CODEWITHSUNDEEP
java
Zeng Cheng
Zeng Cheng

Reputation: 825

Java - Create random permutation without using temporary list

This is the last problem I could not solve:

  1. You are given an array {1,2,3,4,5,6,7,8,9}

Create a function that creates a random permutation without using a temporary list, in Θ(n) time.

Couldn't I use Collections.shuffle function to do this once I get the int[] array? I'm not sure what exactly the problem is asking for. I could do a simple loop where I could randomize it using an iterative method and do a simple check but shuffle would be easier, no?

Upvotes: 0

Views: 151

Answers (1)

SME_Dev
SME_Dev

Reputation: 1890

In pseudo code:

index1 = 0
index2 = 0
loop: when index1 < array.length
         index2=random[index1,array.length]
         print[array[index2]
         swap[index1,index2]
         index1++

In Java:

int x = 0;
int y = 0;
Random r = new Random();

while(x < array.length){

    y = x + r.nextInt(array.length-x);
    System.out.println(array[y]);

    int temp = array[x];
    array[x] = array[y];
    array[y] = temp;

    x++;
}

Upvotes: 2

Related Questions