Java: Generate a Powerset

Question

This could be language agnostic/helpful answers could just be in pseudo-code.

I have a program that I would like to test under a range of inputs. This program takes a set of files, one of which is designated as the root. I want to run the program with all possible subsets of files. (Two subsets, containing the same files, but with different roots, are considered to be different.)

Here's a same example. Say I have files A, B, and C. I would want to test with:

{A}, root = A
{B}, root = B
{C}, root = C
{A B}, root = A
{A B}, root = B
{B C}, root = B
{B C}, root = C
{A C}, root = A
{A C}, root = C
{A B C}, root = A
{A B C}, root = B
{A B C}, root = C

and so on. I believe this would be the powerset.

What is the best way to generate this set in Java, given a directory full of files?

http://stackoverflow.com/questions/873413/nonrecursively-generating-all-possible-permutations-of-elements-from-two-arrays — Jim Ferrans, Nov 04 '09 at 05:05

score 2 · Answer 1 · answered Nov 04 '09 at 03:05

2

You said Java, but please take a look on this: Permutations, Combinations, and Variations using C# Generics.

answered Nov 04 '09 at 03:05

Rubens Farias

57,174
8
131
162

score 1 · Answer 2 · answered Nov 04 '09 at 03:31

1

Here's pseudocode for a recursive approach to doing tests on all possible mixes.largest-subsets-first:

allofthem = set(listallfiles(thedir))

function trythemall(someset):
  if someset is empty: return
  for entry in someset:
    dotest(someset, root=entry)
  for entry in someset:
    trythemall(someset - set([entry]))

trythemall(allofthem)

Not hard to reorg if you want smallest subsets first, of course.

answered Nov 04 '09 at 03:31

Alex Martelli

854,459
170
1,222
1,395

this would work, but I actually realized my specification of the problem was incorrect. See above. – Nick Heiner Nov 04 '09 at 04:46
OK, I've seen your edit, it seems to me that the difference in what I'm proposing is that in my pseudocode some subsets are presented more than once -- if that's your issue please clarify and I'll propose ways to address it, tx! – Alex Martelli Nov 04 '09 at 05:04
the problem, I believe, is that there are subsets that will not be generated by your solution. – Nick Heiner Nov 04 '09 at 13:30
@Rosarch, I think you're wrong there -- doing the obvious/trivial translation to Python I can confirm that all subsets do get generated (though some of the short ones surface more than once) as logic confirms (every subset can be generated by taking some items off the universal set, and this code will exhaustively take away each and every combination -- in fact subsets that take away 2 or more items are generated repeatedly because the items are taken away repeatedly in every possible _order_). Have any counterxample...? – Alex Martelli Nov 04 '09 at 15:32

score 0 · Answer 3 · answered Nov 04 '09 at 03:02

Is this what you are after (psuedocode)?

set = new List()
foreach (file in dir) {
    set.add(file)
    foreach (entry in set) {
        do-test(set, entry)
    }
}

This would build a set, then pass the set and each entry in the set to a do-test method.

Java: Generate a Powerset

3 Answers3