CODEWITHSUNDEEP
javaalgorithmrandomhashtablepermutation
NotSure
NotSure

Reputation: 681

Writing a method that outputs a different uniqe permutation of a number every time it's called

I got this interview question and I am still very confused about it. The question was as the title suggest, i'll explain.

You are given a random creation function to use.

the function input is an integer n. let's say I call it with 3.

it should give me a permutation of the numbers from 1 - 3. so for example it will give me 2, 3 , 1.

after i call the function again, it won't give me the same permutation, now it will give me 1, 2, 3 for example.

Now if i will call it with n = 4. I may get 1,4,3,2.

Calling it with 3 again will not output 2,3,1 nor 1,2,3 as was outputed before, it will give me a different permutation out of the 3! possible permutations.

I was confused about this question there and I still am now. How is this possible within normal running time ? As I see it, there has to be some static variable that remembers what was called before or after the function finishes executing. So my thought is creating a static hashtable (key,value) that gets the input as key and the value is an array of the length of the n!. Then we use the random method to output a random instance out of these and move this instance to the back, so it will not be called again, thus keeping the output unique.

The space time complexity seems huge to me. Am I missing something in this question ?

Upvotes: 2

Views: 124

Answers (2)

Pedro
Pedro

Reputation: 1072

Jonathan Rosenne's answer was downvoted because it was link-only, but it is still the right answer in my opinion, being that this is such a well-known problem. You can also see a minimal explanation in wikipedia: https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order.

To address your space-complexity concern, generating permutations in lexicographical ordering has O(1) space complexity, you don't need to store nothing other than the current permutation. The algorithm is quite simple, but most of all, its correctness is quite intuitive. Imagine you had the set of all permutations and you order them lexicographically. Advancing to the next in order and then cycling back will give you the maximum cycle without repetitions. The problem with that is again the space-complexity, since you would need to store all possible permutations; the algorithm gives you a way to get the next permutation without storing anything. It may take a while to understand, but once I got it it was quite enlightening.

Upvotes: 1

phflack
phflack

Reputation: 2727

You can store a static variable as a seed for the next permutation

In this case, we can change which slot each number will be put in with an int (for example this is hard coded to sets of 4 numbers)

private static int seed = 0;

public static int[] generate()
{
    //s is a copy of seed, and increment seed for the next generation
    int s = seed++ & 0x7FFFFFFF; //ensure s is positive
    int[] out = new int[4];

    //place 4-2
    for(int i = out.length; i > 1; i--)
    {
        int pos = s % i;
        s /= i;
        for(int j = 0; j < out.length; j++)
            if(out[j] == 0)
                if(pos-- == 0)
                {
                    out[j] = i;
                    break;
                }
    }

    //place 1 in the last spot open
    for(int i = 0; i < out.length; i++)
        if(out[i] == 0)
        {
            out[i] = 1;
            break;
        }

    return out;
}

Here's a version that takes the size as an input, and uses a HashMap to store the seeds

private static Map<Integer, Integer> seeds = new HashMap<Integer, Integer>();

public static int[] generate(int size)
{
    //s is a copy of seed, and increment seed for the next generation
    int s = seeds.containsKey(size) ? seeds.get(size) : 0; //can replace 0 with a Math.random() call to seed randomly
    seeds.put(size, s + 1);
    s &= 0x7FFFFFFF; //ensure s is positive
    int[] out = new int[size];

    //place numbers 2+
    for(int i = out.length; i > 1; i--)
    {
        int pos = s % i;
        s /= i;
        for(int j = 0; j < out.length; j++)
            if(out[j] == 0)
                if(pos-- == 0)
                {
                    out[j] = i;
                    break;
                }
    }

    //place 1 in the last spot open
    for(int i = 0; i < out.length; i++)
        if(out[i] == 0)
        {
            out[i] = 1;
            break;
        }

    return out;
}

This method works because the seed stores the locations of each element to be placed

For size 4:

  1. Get the lowest digit in base 4, since there are 4 slots remaining
  2. Place a 4 in that slot
  3. Shift the number to remove the data used (divide by 4)
  4. Get the lowest digit in base 3, since there are 3 slots remaining
  5. Place a 3 in that slot
  6. Shift the number to remove the data used (divide by 3)
  7. Get the lowest digit in base 2, since there are 2 slots remaining
  8. Place a 2 in that slot
  9. Shift the number to remove the data used (divide by 2)
  10. There is only one slot remaining
  11. Place a 1 in that slot

This method is expandable up to 12! for ints, 13! overflows, or 20! for longs (21! overflows)

If you need to use bigger numbers, you may be able to replace the seeds with BigIntegers

Upvotes: 1

Related Questions