Selecting elements from an unknown numer of sets

Question

I want to list all possible combinations that result from selecting at-least one and atmost all elements from each set out of a number(unknown) of sets input by user. An element may be in more than one set but listing it more than once is not a problem.

Eg:- If the user enters 3 sets as

{1,3,5}
{2,4}
{1}

Output

1,2,1
1,4,1
1,2,4,1
3,2,1
3,4,1
3,2,4,1
5,2,1
5,4,1
5,2,4,1
1,3,2,1
1,3,4,1
1,3,2,4,1
1,5,2,1
1,5,4,1
1,5,2,4,1
3,5,2,1
3,5,4,1
3,5,2,4,1
1,3,5,2,1
1,3,5,4,1
1,3,5,2,4,1

C# code will be even more helpful. Thanks.

It looks as if you want the *cartesian product* of the *power sets* of your input sets, with the wrinkle that you are not interested in including the empty set which, formally, is a member of the power set of any set. I have emphasised two terms, a search on SO will produce algorithms, probably also C# code, for these operations. — High Performance Mark, May 28 '12 at 16:22
As a rep-whore I've turned my comment into an answer so that you can accept it -- and allow the rest of my peers either to admire my wisdom or chew on the bitter weeds of disappointment and downvote me. — High Performance Mark, May 29 '12 at 10:50

score 1 · Accepted Answer · answered May 29 '12 at 10:49

It looks as if you want the cartesian product of the power sets of your input sets, with the wrinkle that you are not interested in including the empty set which, formally, is a member of the power set of any set. I have emphasised two terms, a search on SO will produce algorithms, probably also C# code, for these operations.

score 0 · Answer 2 · answered May 28 '12 at 16:47

somthing like this: (a set do not contains duplicates)

def permutate(set_to_perm, perm):
    Boolean used; 

    for elemen_set_  in set_to_perm:
        used = false

        for element_perm in perm
             if element_set_ == element_perm:
                 used = true;
                 break;
        if used false:
           if lengh(set_to_perm) < lenght(perm)
               permutate(set_to_perm, append element_set_ to perm)
           else:
               print per

take input from user;
set_to_perm = make a set from user input;
permutate(set_to_perm,[]):

score 0 · Answer 3 · answered May 28 '12 at 17:25

You can enumerate all the sets you require with a recursive algorithm:

 current_set = { }

 enumerate (list_of_sets):
    if (list_of_sets is empty):
       REPORT current_set
    f = list_of_sets.front()
    r = list_of_sets.tail() /* all sets except f */
    n = f.size()
    for (i = 0 .. n - 1):
       current_set.insert(f[i])
       rec (f, i + 1, r)
       current_set.remove(f[i])

 rec (set, index, remaining_sets):
    if (index == set.size()):
       enumerate(remaining_sets)
    else:
       current_set.insert(f[index])
       rec(set, index + 1, remaining_sets)
       current_set.remove(f[index])
       rec(set, index + 1, remaining_sets)

score 0 · Answer 4 · answered May 28 '12 at 22:58

by F#

let rec comb n l =
  match n, l with
  | 0, _  -> [[]]
  | _, [] -> []
  | n, x::xs -> List.map (fun l -> x ::l) (comb (n - 1) xs) @ (comb n xs)

let powersets xs = seq {
    for i = 1 to List.length xs do
      for x in comb i xs -> x
  }

let rec powerset_out xs (acc:int list list) =
  if List.isEmpty xs then
    System.String.Join(",", seq { for el in acc do yield! el })
    |> printfn "%s"
  else
    let x::xs = xs
    for el in powersets x do
      powerset_out xs (acc @ [el])

Execution example:

> powerset_out [[1;3;5];[2;4];[1]] [];;
1,2,1
1,4,1
1,2,4,1
3,2,1
3,4,1
3,2,4,1
5,2,1
5,4,1
5,2,4,1
1,3,2,1
1,3,4,1
1,3,2,4,1
1,5,2,1
1,5,4,1
1,5,2,4,1
3,5,2,1
3,5,4,1
3,5,2,4,1
1,3,5,2,1
1,3,5,4,1
1,3,5,2,4,1

Selecting elements from an unknown numer of sets

4 Answers4