Prolog: trouver tous les numéros de chiffres uniques qui peuvent être formés à partir d'une liste de chiffres

Question

La meilleure chose que je pouvais venir avec à ce jour est cette fonction:

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

où digit/1 est une fonction vérifiant si un atome est un chiffre décimal.

Le numberFromList(List, N) trouve tous les numéros qui peuvent être formés avec tous chiffres de List.
Par exemple. [2, 3] -> 23, 32. mais je veux obtenir ce résultat: [2, 3] -> 2, 3, 23, 32

J'ai passé beaucoup d'heures à réfléchir à ce sujet et je soupçonne que vous pouvez utiliser quelque chose comme append(L, _, List) à un moment donné pour obtenir des listes de moindre longueur.

J'apprécierait toute contribution.

Answer 1

Il vous manque cas lorsque vous passez chiffres de la liste.

 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, comme @Roland Illig mentionné il y a select(X, List, LX) pour remplacer member(X, List), delete(List, X, LX)

Answer 2

Le unique/3 prédicat génère toutes les listes de longueur jusqu'à MaxLen comprenant des symboles de Symbols. Les listes générées sont stockées dans L, une fois à la fois.

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

Le prédicat auxiliaire pour générer les listes.

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

Un programme simple pour démontrer le prédicat ci-dessus:

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

Answer 3

Voici une façon, en utilisant SWI-Prolog built-ins pour atomic_list_concat/2 , atom_number/2 et select/3 . Tout d'abord, le point d'entrée fait référence à une mise en oeuvre à l'aide d'un accumulateur initialement vide:

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

Le numberFromList/3 prédicat soit accumule chiffres (non vérifiées) dans la liste, ou non, en laissant choicepoints:

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

La clause finale de numberFromList/3 permute la liste cumulée de chiffres et les concatène en un atome, qui est ensuite converti en un certain nombre, si nécessaire:

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

Parfois permute/2 (tel que défini à la main ci-dessous) peut être disponible sous forme intégrée, comme permutation/2 . Voici une définition manuelle à l'aide select/3 :

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

Si vous voulez une liste de tous les résultats et ne veulent pas se numberFromList/2 machine arrière, vous pouvez envelopper l'appel à numberFromList/3 (avec l'accumulateur vide dans la première clause de numberFromList/2) dans un findall/3 appel.