Thursday, March 26, 2015

Generating a unique permutation of an array

I had a requirement to generate a mixed sequence of lists. The simplest way to explain what I wanted to do was to generate all the permutations of a list and then use a unique permutation for specific test cases. Googling "generate combinations of a list" yielded some good results, except that I didn't want to generate every single combination and select one permutation. I wanted to only generate one permutation and use that.

I ended up just shuffling the array with a seed. The seed was based on a counter. This satisfied my use case "enough". But I really wanted to solve this problem. The problem is:

Given a list (say, 1, 2, 3), and a sequence number from 0..factorial(len(list)), write a linear runtime O(n) function such that perm(sequence) yields some unique permutation of the list.

A crazy idea occurred to me over a sleepless night. What if I were able to come up with a sequence of swaps based on the modulus of a sequence number that could generate a unique permutation of a list? I came up with a silly idea of using the modulus of the sequence number against the position of the array and swapping the two elements. If the modulus was zero, skip. If the modulus is 1, swap this element and the next element. If the modulus is 2, swap this element and the second element over. Then, shift to the next element and swap again. It's better if I describe what I did by hand the next morning:

Starting with 1,2,3 and sequence 0: no swaps (by definition)

Starting with 1,2,3 and sequence 1: position 1 1 mod 4 is 1, swap to get 2,1,3. Position 2 1 mod 3 is 1, swap to get 2,3,1. Done

Starting with 1,2,3 and sequence 2: position 1 2 mod 4 is 0, no swap to get 1,2,3. Position 2 2 mod 3 is 1, swap to get 1,3,2. Done

Starting with 1,2,3 and sequence 3: position 1 3 mod 4 is 3, swap to get 3,2,1. Position 2 2 mod 4 is 0, no swaps to get 3,2,1. Done.

And so on. It worked! I wrote a quick program in python:

def generatecombination(number=0,mytuple=()):  for i in range(0,len(mylist)-1):    modulus = number % (len(mylist) - i)    if modulus > 0:      swap(i,i+modulus,mylist)

Ran it for a list of 3 elements and impressive city:

[1, 2, 3]
[2, 3, 1]
[3, 2, 1]
[1, 3, 2]
[2, 1, 3]
[3, 1, 2]

It correctly generates each permutation in linear time. Success. Run it with four elements and it fails (elements are sorted to make it easier to find -- the actual order from the algorithm is different):

[1, 2, 3, 4]
[1, 3, 2, 4]
[1, 4, 3, 2]
[2, 1, 4, 3]
[2, 3, 4, 1]
[2, 4, 1, 3]
[3, 1, 2, 4]
[3, 2, 1, 4]
[3, 4, 1, 2]
[4, 1, 2, 3]
[4, 2, 1, 3]
[4, 3, 1, 2]

Each of these sequences is generated twice. This is very suspicious because there are 12 (of 24) sequences represented and 4*3 == 12. Some obvious permutations are missing, for example, 4,3,2,1 (the reverse of the original) is missing.

Suspciouser indeed, running it for 5 elements yielded 60 unique elements duplicated twice (5! == 120, 5*4*3 = 60). So my algorithm has a weakness, and the weakness is that it seems to generate only (n-1)! combinations.

def generatecombination(number=0,mytuple=()):
  if number >= (len(mylist)*(len(mylist)-1)):    mylist = mylist[::-1] 
  for i in range(0,len(mylist)-1):    modulus = number % (len(mylist) - i)    if modulus > 0:      swap(i,i+modulus,mylist)

Aha, I thought, I could double the amount of sequences by reversing the starting elements whenever we get higher than n*n-1. Well, almost:

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]

That's only 12+6==18 combinations, so we're still off by a certain amount. At least 4,3,2,1 exists.

Does anyone know why this algorithm works at all? Does anyone know why it fails? What am I missing?

Wednesday, March 25, 2015

Python: pass by value or reference?

If you Google for "python pass by value" (or reference), you'll find a lot of tortured discussion about whether python passes by object reference or not. Some will even prevaricate and say "neither". I finally realised what python was doing just by looking at a question on stackexchange:

Someone had asked why "somelist = someotherlist" was causing both lists to be modified. Someone posted that when you assign "a = b", you've just updated the object reference and they are the same object now. Then it dawned on me how python works, so I came up with the following example:

In C, a variable is a pointer to memory. So when you say:

a = 5;
a = 6;

When you are done, a (memory pointing to value) is 6. There is no "5" because that value was overwritten. In python when you do the above, you get two values and one reference. The variable a references object "6" and object "5" is orphaned.

 I diagrammed the following:

You can see that python doesn't change the value, just the reference. And this is why assignments in python are not always doing what you naively believe. That is why passing a list around in python is easy and works without return values or worrying about scope.

What if you want to pass by value? You have to use an immutable object (like a string or a tuple). If you want to use numbers, you probably have to make a copy.

Weekly writing output

Wordcount graph
Powered by WritersDB.com