How permute works?

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

How permute works?

pliens
Hi all,

I'm trying to understand how the ".permute" method works.
Any hints on the algorithm behind it?

Thanks a lot,
Thomas
Reply | Threaded
Open this post in threaded view
|

Re: How permute works?

pliens
Half-answering my own question...

by looking at Array's Class definition, i saw that the ".permute" method calls the "_ArrayPermute" primitive.

I have no C++ experience, but looking up the source code on GitHub (http://bit.ly/2rexD3a) i found the code snipet that is being called (pasted below).
Could anybody explain the permutation bit somehow?

Thanks and bests,
Thomas


int prArrayPermute(struct VMGlobals *g, int numArgsPushed)
{
        PyrSlot *a, *b, *slots1, *slots2, temp;
        PyrObject *obj1, *obj2;
        int i, j, m, z, size;

        a = g->sp - 1;
        b = g->sp;
        if (NotInt(b)) return errWrongType;

        obj1 = slotRawObject(a);
        size = obj1->size;
        obj2 = instantiateObject(g->gc, obj1->classptr, size, false, true);
        obj2->size = size;
        slots1 = obj1->slots;
        slots2 = obj2->slots;
        memcpy(slots2, slots1, size * sizeof(PyrSlot));
        z = slotRawInt(b);
        for (i=0, m=size; i<size-1; ++i, --m) {
                j = i + sc_mod((int)z, (int)(size-i));
                z = sc_div(z,size-i);
                slotCopy(&temp,&slots2[i]);
                slotCopy(&slots2[i],&slots2[j]);
                slotCopy(&slots2[j],&temp);
        }
        SetRaw(a, obj2);
        return errNone;
}
Reply | Threaded
Open this post in threaded view
|

Re: How permute works?

James McCartney
In reply to this post by pliens
An array of size N has factorial(N) permutations.
The nthPermutation parameter is taken as an index into all possible permutations.
For each position in the output list the corresponding factor of the factorial is used to determine which item to choose.

On Wed, May 10, 2017 at 9:39 AM, <[hidden email]> wrote:
Hi all,

I'm trying to understand how the ".permute" method works.
Any hints on the algorithm behind it?

Thanks a lot,
Thomas



--
View this message in context: http://new-supercollider-mailing-lists-forums-use-these.2681727.n2.nabble.com/How-permute-works-tp7632241.html
Sent from the SuperCollider Users New (Use this!!!!) mailing list archive at Nabble.com.

_______________________________________________
sc-users mailing list

info (subscription, etc.): http://www.birmingham.ac.uk/facilities/ea-studios/research/supercollider/mailinglist.aspx
archive: http://www.listarc.bham.ac.uk/marchives/sc-users/
search: http://www.listarc.bham.ac.uk/lists/sc-users/search/



--
--- james mccartney
Reply | Threaded
Open this post in threaded view
|

Re: How permute works?

lfsaw
interesting...


we had quite some discussion around this over here:

https://github.com/supercollider/supercollider/issues/2687


:)
        Till


> On 15. May 2017, at 05:40, [hidden email] wrote:
>
> An array of size N has factorial(N) permutations.
> The nthPermutation parameter is taken as an index into all possible permutations.
> For each position in the output list the corresponding factor of the factorial is used to determine which item to choose.
> The basic idea is explained here: https://en.wikipedia.org/wiki/Factorial_number_system
>
> On Wed, May 10, 2017 at 9:39 AM, <[hidden email]> wrote:
> Hi all,
>
> I'm trying to understand how the ".permute" method works.
> Any hints on the algorithm behind it?
>
> Thanks a lot,
> Thomas
>
>
>
> --
> View this message in context: http://new-supercollider-mailing-lists-forums-use-these.2681727.n2.nabble.com/How-permute-works-tp7632241.html
> Sent from the SuperCollider Users New (Use this!!!!) mailing list archive at Nabble.com.
>
> _______________________________________________
> sc-users mailing list
>
> info (subscription, etc.): http://www.birmingham.ac.uk/facilities/ea-studios/research/supercollider/mailinglist.aspx
> archive: http://www.listarc.bham.ac.uk/marchives/sc-users/
> search: http://www.listarc.bham.ac.uk/lists/sc-users/search/
>
>
>
> --
> --- james mccartney


_______________________________________________
sc-users mailing list

info (subscription, etc.): http://www.birmingham.ac.uk/facilities/ea-studios/research/supercollider/mailinglist.aspx
archive: http://www.listarc.bham.ac.uk/marchives/sc-users/
search: http://www.listarc.bham.ac.uk/lists/sc-users/search/
Reply | Threaded
Open this post in threaded view
|

Re: How permute works?

pliens
Thanks James and Till.

Seeing the simplified algorithm in the github discussion was very helpful.

I have to say that it is a very difficult-to-grasp bit of logic there..

For sake of future reference, i post Julian's sclang-version of the algorithm here, (slightly corrected):

(
p = {
        |arr, n|
        var j, size;
        size = arr.size; // i changed arr.lastIndex to arr.size
        size.do{ |i|
                j = i + (n % size);
                n = n div: size;
                arr.swap(i, j);
        };
        arr
}
);


p.((0..6),24);
permute((0..6),24)


All the best,
Thomas
Reply | Threaded
Open this post in threaded view
|

Re: How permute works?

James McCartney


On Sun, May 21, 2017 at 10:40 AM, <[hidden email]> wrote:
Thanks James and Till.

Seeing the simplified algorithm in the github discussion was very helpful.

I have to say that it is a very difficult-to-grasp bit of logic there..

For sake of future reference, i post Julian's sclang-version of the
algorithm here, (slightly corrected):

(
p = {
        |arr, n|
        var j, size;
        size = arr.size; // i changed arr.lastIndex to arr.size
        size.do{ |i|
                j = i + (n % size);
                n = n div: size;
                arr.swap(i, j);
        };
        arr
}
);

Old thread...
I don't think this is the same as the algorithm in the primitive.  In the above it is doing modulo the same size each time. 
To implement factorial number system, the modulo needs to be by decreasing size each time.That is why it is size-i, it decreases each time through the loop.
j = i + sc_mod((int)z, (int)(size-i));
 


--
--- james mccartney
Reply | Threaded
Open this post in threaded view
|

Re: How permute works?

brianlheim
On Tue, Jul 11, 2017 at 10:45 PM, <[hidden email]> wrote:

On Sun, May 21, 2017 at 10:40 AM, <[hidden email]> wrote:

(
p = {
        |arr, n|
        var j, size;
        size = arr.size; // i changed arr.lastIndex to arr.size
        size.do{ |i|
                j = i + (n % size);
                n = n div: size;
                arr.swap(i, j);
        };
        arr
}
);

Old thread...
I don't think this is the same as the algorithm in the primitive.  In the above it is doing modulo the same size each time.

Oof.. I miscopied when I moved to pseudocode in the first comment of that GHub issue. The for loop includes the statement `size-1`, and I mistyped 1 instead of i in the next two lines. That got passed down through the game of telephone to the block quoted above.

Sorry about that.

--
-brian