------art_31915_1123205.1131064474463
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

I was intrigued by your post. It looks really neat. And the memory/cpu time
tradeoff is likely worth it.

I was doing a project called FindMaximumClique (a graph algorithm) which
required me to enumerate and check all combinations (as opposed to your
permutations) of subsets of vertices.

I found something on microsoft.com <http://microsoft.com> that did the
"next" combination. It wasn't as fancy as yours in that it couldn't do
random access or tell you what order the array was sorted in, but you seem
to want to do the permutations in order, so maybe there's an algorithm that
allows you to do that in a simpler fashion using less CPU. The one I'm
talking about was called lexicographical sort order on combinations (to
uniquify the order of a sequence).

See
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dv_vstechart/html/mth_lexicograp.asp
for a description
or
http://msdn.microsoft.com/msdnmag/issues/04/07/TestRun/default.aspx
for the code

It is in C#, and I ported it to Java.

Ammon

On 11/2/05, Daniel Sheppard <daniels / pronto.com.au> wrote:
>
> For a little project I've been doing, I've been playing around with
> permutations of arrays, and came across a couple of interesting methods
> that might want to find their way into facets or one of those other
> libraries that are floating around. I'm not sure if it has any
> application outside of trying to save disk/memory space, but here goes.
>
> Part of what I want to do involves storing information about all the
> different permutations of an array - the problem with this is that I'm
> writing the same data repeatedly, just in different orderings. Take for
> example, an array of 4 integers, sorted into all the permutations:
>
> [1, 2, 3, 4]
> [1, 2, 4, 3]
> [1, 3, 2, 4]
> ..
> [4, 2, 3, 1]
> [3, 4, 2, 1]
> [4, 3, 2, 1]
>
> There's the same array 24 different times. Instead, using my new magic
> "permutation_number" and "permute" methods, a unique number between 0
> and 23 can be assigned to each sort ordering and that can be stored
> instead. So, instead of storing "N! * N * fields" bytes, I only need to
> store "N! * integers + N * fields". I can also seek into a binary file
> based on the sort key to pull out data... which is nice. I don't know if
> there's some famous mathematical formula that proves this, that gives
> these methods a better name, or if they should be called "sort_key" and
> "sort_by_key" or something.
>
> class Array
> def permute(number)
> out = self[0..0]
> nextfactor = factor = 1
> each_with_index {|x,i|
> case i
> when 0: next
> else
> nextfactor = factor * (i+1)
> out.insert(number % nextfactor / factor, x)
> factor = nextfactor
> end
> }
> out
> end
> def permutation_number(original_array=self.sort)
> m = 1
> v = 0
> last_indicies = Hash.new(0)
> original_array.each_with_index {|x,i|
> next if i==0
> m *= i
> done = original_array[0..i]
> v += m * self.select {|y| done.include?(y)}.rindex(x)
> }
> v
> end
> end
>
> [3,1,2,4].permutation_number
> => 19
> [1,2,3,4].permute(19)
> => [4,3,2,1]
>
> It basically works by building up an array from the original. There is 1
> place for the first item, 2 available for the second, 3 for the third,
> etc. So, if you look at the number 19:
>
> 3 * 3! = 18, leaves 1
> 0 * 2! = 0, leaves 1
> 1 * 1! = 1, leaves 0
>
> so we then build up the array, starting with [1].
> We insert the next item at position 1, giving [1,2]
> we insert the next item at position 0, giving [3,1,2]
> we insert the next item at position 3, giving [3,1,2,4]
>
> Like magic it is.
>
> Also, using the same technique, I rewrote the Array.each_permutation
> method from Nano/Facets. This method runs about 25-30% slower, but it
> uses O(N) memory instead of O(N!) memory, and wont fall over from a
> stack overflow if you give it an array that's too long (though it will
> eat your cpu until the end of eternity. Factorials over 10 get pretty
> damn big).
>
> class Array
> def each_permutation()
> perm_count = (1...size).inject(0) { |s,x| s + x * x.factorial }
> weights = Array.new(size-1) {|i| (i+1).factorial }
> s = weights.size
> x,i,v,pos = nil
> 0.upto(perm_count) do |v|
> out = self[0..0]
> each_with_index {|x,i|
> case i
> when 0: next
> when s: out.insert(v / weights[i-1], x)
> else out.insert(v % weights[i] / weights[i-1], x)
> end
> }
> yield out
> end
> end
> end
>
>
>
>
> #####################################################################################
> This email has been scanned by MailMarshal, an email content filter.
>
> #####################################################################################
>
>

------art_31915_1123205.1131064474463--