Prolog: find all numbers of unique digits that can be formed from a list of digits

Question

The best thing I could come up with so far is this function:

 numberFromList([X], X) :-  
    digit(X), !.  
 numberFromList(List, N) :-  
    member(X, List),     
    delete(List, X, LX),  
    numberFromList(LX, NX),  
    N is NX * 10 + X.

where digit/1 is a function verifying if an atom is a decimal digit.

The numberFromList(List, N) finds all the numbers that can be formed with all digits from List.
E.g. [2, 3] -> 23, 32. but I want to get this result: [2, 3] -> 2, 3, 23, 32

I spent a lot of hours thinking about this and I suspect you might use something like append(L, _, List) at some point to get lists of lesser length.

I would appreciate any contribution.

Answer 1

The predicate unique/3 generates all lists of length up to MaxLen consisting of symbols from Symbols. The generated lists are stored in L, once at a time.

unique(MaxLen, Symbols, L) :-
    between(0, MaxLen, Len),
    length(L, Len),
    unique(Symbols, L).

The helper predicate for generating the lists.

unique(_, []).
unique(Set, [H|R]) :-
    select(H, Set, ReducedSet),
    unique(ReducedSet, R).

A simple program for demonstrating the above predicate:

main :-
    unique(5, [2,3], L),
    write(L), nl, fail.

Answer 2

Here's one way, using SWI-PROLOG built-ins for atomic_list_concat/2, atom_number/2 and select/3. Firstly, the entry point refers to an implementation using an initially empty accumulator:

numberFromList(L, N) :-
    numberFromList(L, [], N).

The predicate numberFromList/3 either accumulates digits (unchecked) from the list, or not, leaving choicepoints:

numberFromList([_|Cs], Acc, N) :-
    numberFromList(Cs, Acc, N).
numberFromList([C|Cs], Acc, N) :-
    numberFromList(Cs, [C|Acc], N).

The final clause of numberFromList/3 permutes the accumulated list of digits and concatenates them into an atom, which is then converted to a number as required:

numberFromList([], [C|Cs], N) :-
    permute([C|Cs], PermutedAcc),
    atomic_list_concat(PermutedAcc, AN),
    atom_number(AN, N).

Sometimes permute/2 (as defined manually below) may be available as a built-in, such as permutation/2. Here is a manual definition using select/3:

permute([], []).
permute([E|Es], [E0|PL]) :-
    select(E0, [E|Es], Rem),  
    permute(Rem, PL).

If you want a list of all the results and don't want numberFromList/2 to backtrack itself, you could wrap the call to numberFromList/3 (with the empty accumulator in the first clause of numberFromList/2) in a findall/3 call.

Answer 3

You are missing case when you skip digit from list.

 numberFromList([X], X) :-  
    digit(X), !.  
 numberFromList(List, N) :-
    member(X, List),     
    delete(List, X, LX),
    numberFromList(LX, NX),  
    ( % use X
        N is NX * 10 + X
    ; % skip X
        N = NX
    ).

BTW, as @Roland Illig mentioned there is select(X, List, LX) to replace member(X, List), delete(List, X, LX)