Fog Creek Software
Discussion Board




Finding all n pernumtations of a number

Eg - 123,231,321,132,213,312
I was thinking how to write the code for this, I thought of a recursive solution using queues,
where initially, say we have n numbers
it would look like


q1  q2
() (1234), then a deque from 2nd queue
(1)(234), another deque and enque
(2)(341)
(3)(412) and print the 2 queues
then for each queue on right ie. q2, we would call the same
recursive function with 1 digit less

()(234)
(2)(34)
(3)(42)
(4)(23) -> ()(23) -> (2)(3), (3)(2)
and so on,all the while printing the queue to get the permutatons

pseudo-code will be something like-

//passing the number of digits in array,the right hand queue, and the array containing the number that is
1234 would be {1,2,3,4}

//a1 would be the array containing the leading
//digits, which have been removed in recursive call
permute(int n,Queue q2,int a[] ,int a1[]) {


q1 =new queue(1) //size would be 1 of left queue
q2=new queue(n) //

q1.enque(q2.deque) // set up first combination
//  say (1) (234)
for(int i=0;i<=n-1;i++){

if(n==1) return; //base case alreadt permuted

q1.enque(q2.deque);// becomes (12)(34)
q2.enque(q1.deque);//becomes(2)(341)
print a1. concat print (q1.concat(q2)) //print in this state

//initial case a1 is empty

a1.addelement=a.removeelement(q1) // remove the digit from array which has q1 and put in a1

permute(n-1,q2,a[],a1); //recursive call ,reduce on digit in array


}




Does anybody think this could be asolution to the n permutations problem? I just came out of it from top of my head...it could be garbage, I'm not sure

code
Monday, January 27, 2003

should be finding all permutations of a number ...

code
Monday, January 27, 2003

You could do something like below where you just multiply and get your answer

perm (number) {
    while (number --){
        p *= number
    }   
    return p
}

Stinky
Monday, January 27, 2003

Why not use the standard library?  algo.h and prev_ and next_permutation().

David Blume
Monday, January 27, 2003

I was trying to come up with a recursive solution..
and it was for a programming test in a job interview :)

code
Monday, January 27, 2003

I got that in an interview once except I was given a string of letters and I had to work out how to work out all the legitimate English words in the string. My solution was to work out all the permutations of letters in the string and then lookup each into a dictionary of words (provided for the purpose of the test) and return 'true' if a certain perm was a word.

Wrong Wrong Wrong...

I should have read through the dictionary one by one and then seen if I could make up the word from the dictionary using the string by using simple string manipulation.

I got the job anyway, even though I had the wrong end of the stick...

Been There
Monday, January 27, 2003

*  Recent Topics

*  Fog Creek Home