CS question: Elegent way to calculate map permutations

[dj_d]

Question for the folks who were paying attention in CS 101.

boolean [string] map1;
map1["foo"] = true;
map1["bar"] = true;
map1["baz"] = true;

I'd like to create a new map2 with entries
""
"foo"
"bar"
"baz"
"foobar"
"foobaz"
"barbaz"
"foobarbaz"
Basically, create a map2 that contains all permutations of map1.

Any suggestions?

 

[jasonharper]

Your example shows combinations, not permutations. Assuming that combinations is actually what you meant (which is easier, anyway):

boolean [string] map1;
map1["foo"] = true;
map1["bar"] = true;
map1["baz"] = true;

boolean[string] map2;
int total = 2 ^ count(map1);
for code from 0 to total - 1 {
	buffer b;
	int temp = code;
	foreach piece in map1 {
		if ( temp / 2 * 2 != temp ) {
			// was odd
			b.append(piece);
		}
		temp = temp / 2;
	}
	map2[b.to_string()] = true;
}

foreach key, val in map2 print(key);

r7584 is required for this to work, as the test code uncovered an ASH bug (to_string(buffer) was returning a value that wasn't usable as a map key).

 

[the_great_cow_guru]

if ( temp / 2 * 2 != temp )

That's the strangest oddness test I've ever seen, why not:

if ( temp % 2  == 1 )

 

[dj_d]

Your example shows combinations, not permutations.

Also covered in CS101. Yup, I meant combinations.

7584 is required for this to work, as the test code uncovered an ASH bug (to_string(buffer) was returning a value that wasn't usable as a map key).

I'll pretend this is why I couldn't figure it out for myself.