Неожиданный повторяющийся результат при создании всех комбинаций для n битов

Question

Мне нужно выучить Пролог для Колледжа, и я дал себе задачу решить одну строку Нонограммы (https://en.wikipedia.org/wiki/Nonogram).

Я использую 'x' как ' o 'в качестве символов для заполненного или пустого поля и подхода грубой силы, чтобы в качестве первого шага найти каждую комбинацию в этой строке независимо от правил номограммы. Этот шаг действительно такой же, как поиск каждой комбинации из n битов, например 000 001 010 011 100 101 110 111 с n = 3. Я собираюсь потом отсеять соответствующие комбинации в соответствии с правилами Nomogram, на самом деле этот код уже работает. Это, конечно, неэффективно, но я рад, что дошел до этого.

Если есть очень легкий подход, решить все варианты для линии, в соответствии с правилами для линии, в «вперед» подход, противоположный этому подходу грубой силы, я хотел бы узнать, как это можно сделать. Правила будут выглядеть примерно так (10, [4,3]), то есть в строке будет 10 мест и 2 группы по 4 и 3 блока. Но так как это «просто для удовольствия», не беспокойтесь о его написании, пожалуйста!

Приведенный ниже код работает - но он находит каждую комбинацию дважды, и я не могу понять, почему. Любая идея, что заставляет это перечислить все дважды? Если в этом коде нет мэров (они точно есть!), Пожалуйста, не стесняйтесь указывать на них. Я всего пару часов изучаю язык и все еще пытаюсь «форсировать» стиль для неявных или объектно-ориентированных языков, но без особого успеха:)

count_list([], 0). % Count Elements in a List
count_list([_|T], C) :- 
    count_list(T, C1),
    C is 1 + C1.

append_list(X, [], [X]). % Attach a new Element as first to a List
append_list(X, List, [X|List]).

zeichen(x).
zeichen(o).

nonoline_generator(N, PartIn, Line) :- % Add x and o to the combination, except the last one
    count_list(PartIn, C),
    N > C + 1,
    zeichen(X),
    append_list(X, PartIn, PartAppended),
    nonoline_generator(N, PartAppended, Line).
nonoline_generator(N, PartIn, Line) :- % Add the last x or o to the line
    count_list(PartIn, C),
    N =:= C + 1,
    zeichen(X),
    append_list(X, PartIn, Line).

% Usage:
nonoline_generator(2, [], Out).
% gives (well... all double, at the moment)
% [x,x]
% [x,o]
% [x,x]
% [x,o]
% [o,x]
% [o,o]
% [o,x]
% [o,o]

Большое спасибо за любые комментарии!

Answer 1

Если все, что вы хотите сделать, это заполнить список с x или o:

bits([]).
bits([x|Rest]) :- bits(Rest).
bits([o|Rest]) :- bits(Rest).

?- length(B, 3), 
   forall(bits(B), 
          format('~q~n', [B])).
[x,x,x]
[x,x,o]
[x,o,x]
[x,o,o]
[o,x,x]
[o,x,o]
[o,o,x]
[o,o,o]