How to get all possible permutations

[drdaco]

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 :)

[Salem]

> 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.

[monkey_king]

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

[Deque]

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.

[sloan31]

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.

public static String nextSubset(String subset) {
        //Step 1  (initialization)
        StringBuffer buffer = new StringBuffer(subset);
        int k = buffer.length();

        // Step 2 (look for rightmost 0)
        while((k >= 1) && (buffer.charAt(k - 1) == '1') ) {
            k--;
        }

        // Step 3 (if there is a zero, form the next string)
        if(k >= 1) {
            buffer.setCharAt(k - 1, '1');

            for(int j = k + 1; j <= buffer.length(); j++) {
                buffer.setCharAt(j - 1 , '0');
            }
            return buffer.toString(); }
        else
            return buffer.toString();


    }

[drdaco]

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

[drdaco]

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

[Deque]

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

[drdaco]

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

[aliannahfth]

Thanks for your informations

[prime1999]

At least for n<30 bits (which is probably near the maximum on one fast processor), you could just have a for loop from 0 to 2^n and get the binary representation for each number.

[mediastar]

It is just to count from 0 to a specified number and then convert all results so obtained into binary strings with enough heading 0s to make them of equal-length. The trouble is you can write fast codes with integer variables but you have to use float variables if the maximum number overflows integer limit of your computer.

[prime1999]

But obviously going through numbers from 0 to 2^n would exceed time limit way before it exceeds the limit of a long int.

[jameskodo85]

I lately did something like to help me solve a kneel problem You may be concerned in my java method here whip can take a string of 0s and 1s and generate the next set value So basically, just pass it the letter string of all 0s(the empty subset) and apply this method in a loop to generate all potential personality.

[arkoenig]

I hate to sound smug, but this is not a difficult problem. In effect, you have a string of 0's and 1's that you want to treat as a binary number, and you want to add 1 to it repeatedly.

Adding 1 to a binary number is easy: Take all the consecutive 1's at the low-order end, change them to 0, and change the 0 immediately before that to 1. As an example, consider 001010110100111. There are 3 1's at the low-order end, so you change them to 0's and change the 0 before that to 1, yielding 001010110101000.

Let's see how this process works for three digits.

You start with 000. There are no 1's at the end, so there's nothing to change; but you have to change the 0 before that empty string of 1's to a 1, yielding 001.

For 001, you have to change the 1 at the end to 0 and the 0 before that to 1, giving 010. The next steps yield 011, 100, 101, 110, and 111 in turn.

At the last step, you would have to change all the 1's to 0, but there's no 0 before that so you can't complete the process. That is your signal that you are done.

Of course, as others have pointed out, the number of steps you will have to go through is 2^n where n is the number of bits in your number. This gets out of hand rather quickly. Nevertheless, this description shows how to do it if you have time.

[Ryuukai]

Not so long, i coded your soluttion and it took only a few minutes to go thru all 2^32 numbers.
BTW, what the original poster was asking was for Conbinations (with repetitions), not permutations.

#include <stdio.h>
#include <string.h>

#define MAX_DIGITS 32

int main(void)
{
	const int Setup0 = MAX_DIGITS-1;
	int count, i;
	char data[MAX_DIGITS+1];
	FILE *fpout = fopen("binary-perms.txt", "w");
	
	memset(data, '0', sizeof(data));
	data[MAX_DIGITS] = '\0';
	
	i = Setup0;
	
	for (count = 0; count <= 20000; count++ )
	{
		data[i] = '1';
		if (i != Setup0) {
			memset(data+i+1, '0', Setup0-i);
			i = Setup0;
		}
		else // i == Setup0
			for (	; i >= 0 && data[i] != '0'; i--);

//		fprintf(fpout, "%s\n", data);
	}

	printf("Generated %d permutations\n", count);
	
	return 0;
}

[JeffGrigg]

Hint: The Java bit operators are the C bit operators.

The history is...
K&R C -> Ansi C -> C++ -> Java

(And Java and C++ inspired Microsoft's C#.)

[Adak]