CODEWITHSUNDEEP
prologcombinationspermutationenumeration
Wayne
Wayne

Reputation: 33

generate a big list from a given list by enumeration in prolog

I am trying to generate a big list (2^N elements) from a small given list (N elements). For example, there is a list [X,Y,Z], in which X, Y or Z could only be 0.1 or 0.9. I will pick 0.1 or 0.9 from X, pick 0.1 or 0.9 from Y and pick 0.1 or 0.9 from Z sequentially, then see XYZ as an element of the new list. So there should be 2^N elements in the new list [0.001,0.009,0.009,...,0.729] ([0.1*0.1*0.1, 0.1*0.1*0.9, 0.1*0.9*0.1, ..., 0.9*0.9*0.9]). How can I get this new list from the given list? N is a parameter acquired from the given list,

trn(List_given,Outlist):-
    length(List_given,N),
    ...

I just want to implement like this,

?- trn([X,Y],Out).
Out=[0.01,0.09,0.09,0.81].

Thanks in advance!

Upvotes: 0

Views: 125

Answers (1)

lurker
lurker

Reputation: 58284

To generate the possible combinations of your values:

mem(L, E) :- member(E, L).

gen_values(N, Choices, Values) :-
    length(Values, N),
    maplist(mem(Choices), Values).

So:

| ?- gen_values(3, [0.1, 0.9], L).

L = [0.10000000000000001,0.10000000000000001,0.10000000000000001] ? a

L = [0.10000000000000001,0.10000000000000001,0.90000000000000002]

L = [0.10000000000000001,0.90000000000000002,0.10000000000000001]

L = [0.10000000000000001,0.90000000000000002,0.90000000000000002]

L = [0.90000000000000002,0.10000000000000001,0.10000000000000001]

L = [0.90000000000000002,0.10000000000000001,0.90000000000000002]

L = [0.90000000000000002,0.90000000000000002,0.10000000000000001]

L = [0.90000000000000002,0.90000000000000002,0.90000000000000002]

(1 ms) yes

Then you need a list multiplier:

prodlist(L, P) :-
    prodlist(L, 1, P).

prodlist([X], A, P) :- P is X * A.
prodlist([X,Y|T], A, P) :-
    A1 is X * A,
    prodlist([Y|T], A1, P).

Then you can get all of the results with findall/3:

trn(List_given, Outlist):-
    length(List_given, N),
    findall(X, (gen_values(N, [0.1, 0.9], Values), prodlist(Values, X)), Outlist).

Resulting in:

| ?- trn([_,_,_], Out).

Out = [0.0010000000000000002,0.0090000000000000028,0.0090000000000000011,0.081000000000000016,0.0090000000000000011,0.081000000000000016,0.081000000000000016,0.72900000000000009]

yes
| ?-

You can use trn([X,Y,Z], Out) here, but there's really no point. You could just as well define the predicate with the length: trn(3, Out).

Note, there's some slight floating point precision inaccuracy happening, which yields the long decimals. Also, this method doesn't take advantage of the redundancy in calculations, so it's probably not the most efficient approach. And finally, if N (the length of the input list) is large, this will explode.

Upvotes: 1

Related Questions