CODEWITHSUNDEEP
javafilesetpermutationpowerset
Nick Heiner
Nick Heiner

Reputation: 122450

Java: Generate a Powerset

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?

Upvotes: 0

Views: 1314

Answers (3)

Alex Martelli
Alex Martelli

Reputation: 881705

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.

Upvotes: 1

Rubens Farias
Rubens Farias

Reputation: 57956

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

Upvotes: 2

jheddings
jheddings

Reputation: 27573

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.

Upvotes: 0

Related Questions