CODEWITHSUNDEEP
algorithmrecursionpermutation
JudyJiang
JudyJiang

Reputation: 2227

Permutation of integers from an array given lengh

I was interviewed a problem and after that I tested my code, found it wrong. Not good at recursion. But I can't figure out the problem.

The question is: Given an array range from 0 ~ 9, and a length, for example, 3; generate all permutations of integers from the given array in given length. So, for the example: The permutation should be: 012, 013, 014,..., 345, 346... Below is my java code, where's the problem? (I think it's the index or the offset part) And, if there's any better solution!

public void NumPermutation(int[] list, int offset, int[] temp, int index){
    if(index == 4){
       printarray(temp);
    }

    for(int count = offset; count < list.length; count++){
        temp[index++] = list[count];
        int te = list[offset];
        list[offset] = list[count];
        list[count] = te;
        NumPermutation(list, offset, temp, index);
        index -= 1;
    }
}

public void test(int len){
    int[] list = {0,1,2,3,4,5,6,7,8,9};
    int[] temp = new int[4];
    int index = 0, offset = 0;
    NumPermutation(list, offset, temp,index);
}

The problem is that, the offset may increase each time and it can't even reach the number to the end.

Upvotes: 0

Views: 111

Answers (1)

Bernhard Barker
Bernhard Barker

Reputation: 55609

You need to:

  • Pass offset+1 to the recursive call.

  • Return in the if-statement.

  • Reverse your swap after the recursive call.

  • Replace the 4 with temp.length for a more generic solution.

  • Also preferably replace index++, index, index -= 1 with index, index + 1 and nothing.

Which results in this code: (replaced printarray with a standard print method, assuming this is Java)

public static void NumPermutation(int[] list, int offset, int[] temp, int index){
    if(index == temp.length) {
       System.out.println(Arrays.toString(temp));
       return;
    }

    for(int count = offset; count < list.length; count++){
        temp[index] = list[count];

        // swap
        int te = list[offset];
        list[offset] = list[count];
        list[count] = te;

        NumPermutation(list, offset + 1, temp, index + 1);

        // reverse swap
        te = list[offset];
        list[offset] = list[count];
        list[count] = te;
    }
}

Live demo.

Upvotes: 1

Related Questions