1

I am supposed to write a program in Prolog which when given a list,returns the permutation of its powerset. one thing I forgot to mention: I already have a predicate that reverses a list: deep_reverse(List,RevList). for example: ?-sublist_perm([a,b,c],X). will return:(duplicates are allowed)

 X = [] ;
 X = [c] ;
 X = [b] ;
 X = [b, c] ;
 X = [c, b] ;
 X = [a] ;
 X = [a, c] ;
 X = [c, a] ;
 X = [a, b] ;
 X = [b, a] ;
 X = [a, b, c] ;
 X = [b, a, c] ;
 X = [b, c, a] ;
 X = [a, c, b] ;
 X = [c, a, b] ;
 X = [c, b, a]
false
  • 10,264
  • 13
  • 101
  • 209
Rachel Bernouli
  • 225
  • 2
  • 9
  • 2
    Show us the "bunch of different stuff" you did. – Daniel Lyons Jun 20 '13 at 15:55
  • possible duplicate of [gnu Prolog powerset modification](http://stackoverflow.com/questions/4146117/gnu-prolog-powerset-modification) – Daniel Lyons Jun 20 '13 at 15:56
  • 1
    I looked at it, its not the same. – Rachel Bernouli Jun 20 '13 at 16:02
  • I had one try that was extremely close but it was an ugly code and I deleted all of them trying every time to start over fresh – Rachel Bernouli Jun 20 '13 at 16:03
  • 3
    The third result of a search for permutation finds [this](http://stackoverflow.com/questions/2196570/prolog-how-to-write-and-use-a-function-that-lists-all-list-permutations) with code. The question I linked to above has code for generating a powerset. Spend 30 seconds with both and you can solve the problem yourself. And next time bring your ugly but close code so we don't feel like we're being asked to do your homework for you. – Daniel Lyons Jun 20 '13 at 16:17
  • 2
    Ok thanks I’ll check it out, and yeah next time I promise to bring my code, just don't kill me – Rachel Bernouli Jun 20 '13 at 16:27

1 Answers1

4

You ask two things in one question: How to get all sublists and how to permutate a list:

sublist_perm(In, Out) :-
    sublist(In, Temp),
    permutation(Temp, Out).

sublist([], []).
sublist([_|XS], YS) :-
    sublist(XS, YS).
sublist([X|XS], [X|YS]) :-
    sublist(XS, YS).

See also: man page for permutation/2.

findall(X, sublist_perm([a,b,c], X), XS),
XS = [[],[c],[b],[b,c],[c,b],[a],[a,c],[c,a],[a,b],[b,a],
      [a,b,c],[b,a,c],[b,c,a],[a,c,b],[c,a,b],[c,b,a]].
Kijewski
  • 25,517
  • 12
  • 101
  • 143