Prolog: encontrar todos los números de dígitos únicos que se pueden formar a partir de una lista de dígitos

Question

La mejor cosa que podría llegar a hasta el momento es esta función:

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

donde digit/1 es una función de verificar si un átomo es un dígito decimal.

El numberFromList(List, N) encuentra todos los números que se pueden formar con todos los dígitos de List.
P.ej. [2, 3] -> 23, 32. pero quiero conseguir este resultado: [2, 3] -> 2, 3, 23, 32

Me pasó muchas horas pensando en esto y sospecho que podría utilizar algo así como append(L, _, List) en algún momento obtener listas de menor longitud.

Le agradecería cualquier contribución.

Answer 1

Te faltan caso cuando se salta dígitos de la lista.

 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
    ).

Por cierto, como se ha mencionado @Roland Illig hay select(X, List, LX) para reemplazar member(X, List), delete(List, X, LX)

Answer 2

El unique/3 predicado genera todas las listas de longitud hasta MaxLen que consiste en símbolos de Symbols. Las listas generadas se almacenan en L, una vez a la vez.

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

El predicado ayudante para la generación de las listas.

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

Un programa sencillo para demostrar el predicado arriba:

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

Answer 3

Aquí hay una manera, usando SWI-Prolog muebles empotrados para atomic_list_concat/2 , atom_number/2 y select/3 . En primer lugar, el punto de entrada se refiere a una aplicación utilizando un acumulador inicialmente vacía:

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

El numberFromList/3 predicado ya sea acumula dígitos (no marcado) de la lista, o no, dejando choicepoints:

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

La cláusula final de numberFromList/3 permuta la lista acumulada de dígitos y concatena ellos en un átomo, que luego se convierte a un número según sea necesario:

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

A veces permute/2 (como se define manualmente más adelante) puede estar disponible como un rel incorporado, tal como permutation/2 . He aquí una definición manual utilizando select/3 :

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

Si desea una lista de todos los resultados y no quiere dar marcha atrás numberFromList/2 a sí mismo, que podría envolver la llamada a numberFromList/3 (con el acumulador de vacío en la primera cláusula de numberFromList/2) en un findall/3 llamada.