Ad:

Computer Science Discussion Thread
Unsolved
Views: 4210

Page 1
2
Next

You are currently viewing page 1 of this multi-page discussion thread

Jul 7th, 2009

How to get all possible permutations

Expand Post »

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

Last edited by drdaco; Jul 7th, 2009 at 6:49 pm.

Similar Threads

drdaco

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

6 posts
since May 2009

Permalink

Jul 8th, 2009

Re: How to get all possible permutations

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

Salem

Team Colleague

Reputation Points: 5862

Solved Threads: 950

Posting Sage

Offline

7,164 posts
since Dec 2005

Permalink

Jul 8th, 2009

Re: How to get all possible permutations

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

monkey_king

Reputation Points: 70

Solved Threads: 9

Junior Poster

Offline

160 posts
since Aug 2008

Permalink

Jul 8th, 2009

Re: How to get all possible permutations

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.

Deque

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

5 posts
since Jul 2009

Permalink

Jul 8th, 2009

Re: How to get all possible permutations

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.

java Syntax (Toggle Plain Text)
 
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();
 
 
    }
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();


    }

sloan31

Reputation Points: 14

Solved Threads: 3

Junior Poster in Training

Offline

65 posts
since Apr 2008

Permalink

Jul 8th, 2009

Re: How to get 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

drdaco

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

6 posts
since May 2009

Permalink

Jul 8th, 2009

Re: How to get all possible permutations

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

drdaco

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

6 posts
since May 2009

Permalink

Jul 8th, 2009

Re: How to get all possible permutations

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

Deque

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

5 posts
since Jul 2009

Permalink

Jul 8th, 2009

Re: How to get all possible permutations

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

drdaco

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

6 posts
since May 2009

Permalink

Jul 15th, 2009

Re: How to get all possible permutations

Thanks for your informations

aliannahfth

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

1 posts
since Jul 2009

Page 1
2
Next

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in Computer Science Forum Timeline: string charecter size?

Next Thread in Computer Science Forum Timeline: Having trouble writing pseudocodes.

DaniWeb Message

Cancel Changes

User Name
Password