Subsets in Prolog

by

Here goes an implementation:

subset([], []).
subset([E|Tail], [E|NTail]):-
  subset(Tail, NTail).
subset([_|Tail], NTail):-
  subset(Tail, NTail).

It will generate all the subsets, though not in the order shown on your example.

As per commenter request here goes an explanation:

The first clause is the base case. It states that the empty list is a subset of the empty list.

The second and third clauses deal with recursion. The second clause states that if two lists have the same Head and the tail of the right list is a subset of the tail of the left list, then the right list is a subset of the left list.

The third clause states that if we skip the head of the left list, and the right list is a subset of the tail of the left list, then the right list is a subset of the left list.

The procedure shown above generates ordered sets. For unordered sets you might use permutation/3:

unordered_subset(Set, SubSet):-
  length(Set, LSet),
  between(0,LSet, LSubSet),
  length(NSubSet, LSubSet),
  permutation(SubSet, NSubSet),
  subset(Set, NSubSet).

More Related Contents:

  1. prolog change show answer to print into list
  2. Prolog union for A U B U C
  3. Prolog – count repetitions in list
  4. Prolog removing unique elements only
  5. Find powers of 2 in a list Prolog
  6. pyspark collect_set or collect_list with groupby
  7. Flatten a list in Prolog
  8. How do I append lists in Prolog?
  9. Prolog: Filtering a list?
  10. Remove duplicates in list (Prolog)
  11. Get elements from list of lists
  12. Lazy lists in Prolog?
  13. Segregating Lists in Prolog
  14. Splitting a list of integers into a list of positive integers and a list of negative integers
  15. How to count number of element occurrences in a list in Prolog
  16. Intersection and union of 2 lists
  17. Prolog: First duplicate value
  18. List.shuffle() in Dart?
  19. Implementing “last” in Prolog
  20. Recursive Prolog predicate for reverse / palindrome
  21. Prolog, find minimum in a list
  22. How to generate all the permutations of elements in a list one at a time in Lisp?
  23. Scala list concatenation, ::: vs ++
  24. How to merge YAML arrays?
  25. How to compare a list of lists/sets in python?
  26. Recombining a list of Data.frames into a single data frame [duplicate]
  27. What is the most efficient way to cast a list as a data frame?
  28. “bad words” filter [closed]
  29. Merging two lists in Haskell
  30. What are the differences between vector and list data types in R?

Leave a Comment