This is dumb and I've been banging my head against it for the better part of the day, so perhaps someone here could help me see the light I keep missing.

Let's say I have a string of 0/1's (or heads of tails coins, or yes or nos etc)

For any string length, I need to come up with all the possible permutations these 0/1s can have but none are degenerate. Ex.

say string length = 3

so I can have
0 0 0
1 0 0
0 1 0
0 0 1
1 1 0
1 0 1
0 1 1
1 1 1

the point is that 1 0 0 and 0 0 1 are each unique.

the best I've come up with is to use the degenerates (000, 100, 110, 111) and then use something like next_permutation() to generate the rest. Obviously 000,111 I can skip the procedure.

so that for string of 4:
0000
1000-->next_permutation()
1100-->next_permutation()
1110-->next_permutation()
1111

but I'm wondering if this is the fastest I can do this because I plan to use really LONG strings to generate my permutations...perhaps 1000 chars, so I need something scalable to multiple cores/cpus.

I welcome your ideas

> perhaps 1000 chars, so I need something scalable to multiple cores/cpus.
Try doing the maths first.
Each character you add to the length of the string DOUBLES the amount of time it takes.

If you were blindingly efficient in your code, and could permute every 1nS (a handful of instructions on the fastest processors), you could do a string of 30 characters.

The next 30 chars would take about 30 YEARS to get through.

61 chars -> 60 years
62 chars -> 120 years (are you still interested?)

Or each char DOUBLES the number of machines you need to solve the problem. There isn't enough sand to make enough processors to make any significant dent in this problem.

So you essentially want a truthtable.
The dimension of this truthtable is n*2^n, where n is the number of coin throws.
I once did this program, and I have to agree with you,
it was annoyingly difficult to come up with,
and I never had a beautifull solution.
I think I had 2-loops and 2 extra counters.
the trick is to start from the column1 and then fill up with 1's untill you reach halfway, and then zeroes.
in column2 you would fill up with 1's quaterdown, zeroes till halfdown, 1' till 3quaterdown and 0's the rest

You can use binaries. Start with 000...0, then shift your binary left and add 1 and so on. So you get e.g.:
0000
0001 (shift left --> 0010 plus 1 --> 0011)
0011
0111
1111
You only have to convert this to Strings.

I recently did something similar to help me solve a knapsack problem. You may be interested in my java method here which can take a string of 0s and 1s and generate the next subset value. So basically, just pass it the initial string of all 0s(the empty subset) and use this method in a loop to generate all possible permutations.

thanks everyone, those are good ideas. I had another idea too to make it scalable, and that is to generate just a smaller subset of permutations and then combine to make a bigger set:
a[i] b[j] c[k]
000 | 000 | 000
001 |\ 001 |\ 001
011 |/ 011 |/ 011
111 | 111 | 111

now my algorithm is:
loop over i,j,k to make it easier
000 000 000 --> a[0]+b[0]+c[0]

etc

The binary idea sounds really clean though, can you give me an example? Is there a library I can use or is it staring me in the face this morning? lol

thanks sloan! I was indeed reading the knapsack problem yesterday!! I'll give this a try today

This may help you, if you want to use Java:
http://www.sap-img.com/java/java-bit...-operators.htm

thanks. I'll have to find equivalent libraries in C.

Thanks for your informations