DZone Snippets: permute code

Pyrex

llimllib (Bill Mill) — Tue, 01 Aug 2006 23:11:36 GMT

// description of your code here
Permute a list



cdef class Permute2:



    cdef int n, first

    cdef object lst



    def __init__(self, lst):

        self.lst = lst

        self.first = 0

        self.n = len(lst) - 1



    def __iter__(self):

        return self



    def __next__(self):

        cdef int j, l, k, x, y, z

        if self.first == 0:

            self.first = 1

            return self.lst

        if self.n == 1:

            return [self.lst[1], self.lst[0]]

        while 1:

            if self.lst[-2] < self.lst[-1]:

                self.lst[-2], self.lst[-1] = self.lst[-1], self.lst[-2]

            elif self.lst[-3] < self.lst[-2]:

                if self.lst[-3] < self.lst[-1]:

                    self.lst[-3], self.lst[-2], self.lst[-1] = self.lst[-1], self.lst[-3], self.lst[-2]

                else:

                    self.lst[-3], self.lst[-2], self.lst[-1] = self.lst[-2], self.lst[-1], self.lst[-3]

            else:

                j = self.n - 3

                if j < 0: raise StopIteration

                y = self.lst[j]

                x = self.lst[-3]

                z = self.lst[-1]

                while y >= x:

                    j = j - 1

                    if j < 0: raise StopIteration

                    x = y

                    y = self.lst[j]

                if y < z:

                    self.lst[j] = z

                    self.lst[j+1] = y

                    self.lst[self.n] = x

                else:

                    l = self.n - 1

                    while y >= self.lst[l]:

                        l = l - 1

                    self.lst[j], self.lst[l] = self.lst[l], y

                    self.lst[self.n], self.lst[j+1] = self.lst[j+1], self.lst[self.n]

                k = j + 2

                l = self.n - 1

                while k < l:

                    self.lst[k], self.lst[l] = self.lst[l], self.lst[k]

                    k = k + 1

                    l = l - 1

            return self.lst

Simple Permutation //JavaScript Function

jonasraoni (Jonas Raoni Soares Silva) — Thu, 29 Dec 2005 04:18:25 GMT

[UPDATED CODE AND HELP CAN BE FOUND HERE]

example



var a = ["A", "B", "C", "D"], j = permute(a);

document.write(

    "", a.join(" - "), " = ", j.length, "",

    j.join("
")

);

code



//+ Jonas Raoni Soares Silva

//@ http://jsfromhell.com/array/permute [v1.0]



permute = function(v, m){ //v1.0

    for(var p = -1, j, k, f, r, l = v.length, q = 1, i = l + 1; --i; q *= i);

    for(x = [new Array(l), new Array(l), new Array(l), new Array(l)], j = q, k = l + 1, i = -1;

        ++i < l; x[2][i] = i, x[1][i] = x[0][i] = j /= --k);

    for(r = new Array(q); ++p < q;)

        for(r[p] = new Array(l), i = -1; ++i < l; !--x[1][i] && (x[1][i] = x[0][i],

            x[2][i] = (x[2][i] + 1) % l), r[p][i] = m ? x[3][i] : v[x[3][i]])

            for(x[3][i] = x[2][i], f = 0; !f; f = !f)

                for(j = i; j; x[3][--j] == x[2][i] && (x[3][i] = x[2][i] = (x[2][i] + 1) % l, f = 1));

    return r;

};

Permute //JavaScript Function

jonasraoni (Jonas Raoni Soares Silva) — Fri, 09 Sep 2005 07:20:40 GMT

It permutes elements in an array, the "m" parameter is a boolean which determines if the function should return an array with an "index map" or the real value.

[UPDATED CODE AND HELP CAN BE FOUND HERE]

//+ Jonas Raoni Soares Silva

//@ http://jsfromhell.com/array/permute [v1.0]



permute = function( v, m ){

	for( var j, l = v.length, i = ( 1 << l ) - 1, r = new Array( i ); i; )

		for( r[--i] = [], j = l; j; i + 1 & 1 << --j && ( r[i].push( m ? j : v[j] ) ) );

	return r;

};

Example



document.write( permute( ["A", "B", "C" ], 1 ).join( "
" ), "" );

document.write( permute( ["A", "B", "C" ], 0 ).join( "
" ) );