2
votes

I was trying to permutate using java and i noticed my code works for strings but the same algorithm does not work correctly on Arrays

here's the code for strings

public static void Recurse(String s,int i)
{
    for(int j=i;j<(s.length());j++)
    {   
        s=Swap(s,i,j);
     if(i<(s.length()-1))
     {  
        Recurse(s,i+1); 
     }
        if(i==(s.length()-1))
        {   
            Display(s);        
        }
    }       
}   
   public static String Swap(String newString,int i,int j)
{
    char  newChar[]=newString.toCharArray();
    char temp=newChar[i];
    newChar[i]=newChar[j];
    newChar[j]=temp;

    return String.valueOf(newChar);
}

    public static void Display(String s)
    {
        System.out.println(s);
    }

public static void main(String args[])
{
    String i=new String("123");
    Recurse(i,0);
 }

output: 123 132 213 231 312 321 works fine.

then here is the code for arrays

public static void Recurse(int [] newArray,int i)
{ 
    for(int j=i;j<newArray.length;j++)
    {
    Swap(newArray,i,j);
    if(i<(newArray.length-1))
    {
        Recurse(newArray,i+1);
    }   
    if(i==(newArray.length-1))
    {
        Display(newArray);
    }   

    }   

}

public static void Display(int [] Array)
{
    for(int i: Array)
    {
        System.out.print(i);
    }
    System.out.println();
}


public static void main(String args[])
{
    Recurse(new int[] {1,2,3},0);
}

output 123 132 312 321 123 132

Does not work correctly,So i was wondering what went wrong here.

2
Could you post the code for the Swap method? - GBlodgett
i have reedited the code - user9169047
Are you using the same Swap method for your Array version? - GBlodgett
no,the array was swapped using temp variables,but strings are immutable so i had to convert to charArray then return a new String object to swap the string. - user9169047
You should avoid the String -> char[] -> String conversion. Just operate on char[] and to the from/to String conversion and the beginning/end. - Robert

2 Answers

0
votes

The output seems to be correct with below code:

public static void recurse(int[] newArray, int i) {
    for (int j = i; j < newArray.length; j++) {
        newArray = swap(newArray, i, j);
        if (i < (newArray.length - 1)) {
            recurse(newArray, i + 1);
        }
        if (i == (newArray.length - 1)) {
            display(newArray);
        }
    }
}

private static int[] swap(int[] a, int i, int j) {
    int[] newArray = a.clone();
    int temp = newArray[i];
    newArray[i] = newArray[j];
    newArray[j] = temp;
    return newArray;
}

public static void display(int[] Array) {
    for (int i : Array) {
        System.out.print(i);
    }
    System.out.println();
}


public static void main(String args[]) {
    recurse(new int[]{1, 2, 3}, 0);
}

the output is : 123 132 213 231 312 321

I just made few changes in swap methods code, I made it similar to the one which you used in Strings swap method.

0
votes

Strings are immutable, so when Recurse(String s,int i) calls Recurse(s,i+1);, the value of s remains unchanged.

Arrays are mutable, so when Recurse(int [] newArray,int i) calls Recurse(newArray,i+1);, the value of newArray is changed.

That is why they behave differently.

Note: When I say "the value of" I'm referring to the value of the object, not the value of the reference variable itself.