Outputting a permutation while inputting an inversion vector

Question

I need to know how to print the permutation when I input something such as X = [5 0 1 1 1 2] where 5 = n aka the number of integers following in the array. The output is simple, it'd be J = [5 1 2 4 3]. That is obtained by reading X from the end starting at 2. There are 3 numbers in N (1-5) larger than 2. So J[5] is now 3. Then move in X to the 1 before the 2, there is 1 number in (1-5) - (3(obtained earlier)) in front larger than J[4] so J[4] = 4. If that doesn't make sense because of my explanation this might help, when 3 was removed it is now 1 2 4 5. So if there is to be only 1 element larger than itself it has to be the element 4 because only 5 is larger. I have this so far and I'm confusing myself over coding something that seems so simple.

public static void main(String[] args) {

    int i;
    int j;

    Scanner input = new Scanner(System.in);
    int nums = input.nextInt();

    if (nums < 1 || nums > 1000) {
        input.close();
    } else {
        for (int counter = 0; counter < nums; counter++) {
            int[] a = new int[nums];
            int[] w = new int[nums];
        }
    }
}

I am sorry I don't understand your logic for that particular equation... What are you trying to accomplish because there should be a better way to do what it is you need to do — Ya Wang, Feb 18 '15 at 04:03
input = 5 0 1 1 1 2. 5 = user input for how long array is. output = 5 1 2 4 3. 2 elements in {1..5} > output[5] = 3. 1 element in {1...5} - {3} > output[4] = 4. etc — suislaluna, Feb 18 '15 at 04:09
Why do you have the size of the array at index 0 instead of using array.size? Also, I read this 3 times and still don't know what you are trying to do. — Adrian Leonhard, Feb 18 '15 at 04:58

score 0 · Accepted Answer · answered Feb 18 '15 at 05:29

I will give you an approach on how I would go about this problem.

So the input you receive of this form:

X = [5 0 1 1 1 2];
//5 signifies list of numbers [1,2,3,4,5]
//And the rest of the array i.e. X[1] to X[4] gives us a permutation

Assume you have an ArrayList of n numbers. I have suggested using an arraylist because I find it easier to work with them as we will have to remove elements here.

So initially the arraylist has the following contents (ensure that the elements are entered in an increasing order):

foo = {1,2,3,4,5}; //Assuming the array list is called foo

//The permutation array is [0,1,1,1,2] in your case
//Start traversing it backwards, you can do that with a simple loop
//So given the array a = [0,1,1,1,2], you start with a[4]

a[4] = 2;
//This implies the number you are looking for is at the 3rd last position of the array list

The above is the crux of the solution. Since the array list is sorted and we want to find a number that only has 2 or a[4] numbers larger than it. It's quite simply counting down from 5,4 till we arrive at the 3rd element which is 3. Next you remove that element and get on with the next iteration.

Put simply:

l = foo.size(); //Length of array list initialized before the loop
//If you have a loop starting from i=4 to 0 for the array [0,1,1,1,2]
//At any i, you do:
index = l - a[i];
System.out.print(foo.get(index)); 
//This would ultimately output 3 4 2 1 5 in your case

foo.remove(index); //Remove the element at this index from arraylist
l = l-1; //Since at every iteration we will remove one element

In essence, it's just using the permutation to find the right index of the element in a sorted arraylist and removing it and going ahead with the iterations. I hope I was able to explain myself clearly and this gets you started in the right direction.

PS: I already provided some starting point for your code, should be a good exercise for you to give this a try.

Though when I try something like index = l - a[i] i get an error such as "expression must be an array type but resolves to arraylist? — suislaluna, Feb 18 '15 at 14:51
@suislaluna, I have not been able to test the code that I have provided which is why I only gave you an approach. As I mentioned in my answer `foo` is supposed to be an array list and `a` is the array containing `[0,1,1,1,2]` — Vivek Pradhan, Feb 18 '15 at 15:14
I hope you could get it to work. There might have been some mismatch of data types for arrays and arraylists. Arraylists can be defined of type `Integer` which is not same as `int`. [This](http://stackoverflow.com/questions/14421943/java-arraylist-for-integers) SO Post might come in handy for working with ints in arraylists. — Vivek Pradhan, Feb 19 '15 at 05:46

Outputting a permutation while inputting an inversion vector

1 Answers1