nav[aria-label="Primary Navigation"] { padding: 0; & ul { list-style: none; width: 100%; display: flex; flex-direction: row; justify-content: start; align-items: start; gap: 30px; padding: 0; & li { margin: 0; } & ul li { list-style: none; } } }

JSL Help: How to create all permutations of a vector or a list

MathStatChem

I am trying to figure out the best way to write some JSL to enumerate all the permutations of a vector or list.

One algorithm I've found, that looks promising, is Heap's Algorithm https://en.wikipedia.org/wiki/Heap%27s_algorithm , but I just can't seem to figure out how to code this up. Can someone help me out here?

I realize that the larger the size of a vector or list, the size of the output would grow factorially (number of permutations of k items is k! ), so I'm also interested in a way to generate each item in the list of permutations and do an operation on that permutation and then discard it when it is no longer needed to generate the next permutation(s).

Accepted answers

txnelson

I converted the non recursive form of the code to JMP. See if this helps

generate = Function( {n, A}, 
    //c is an encoding of the stack state. c[k] encodes the for-loop counter for when generate(k+1, A) is called
	
	c = {};

	For( i = 1, i <= n, i++, c[i] = 1 );
	Print( A );
    
    //i acts similarly to the stack pointer
	i = 1;
	While( i <= n,
		If( c[i] < i,
			If( Mod( i, 2 ) == 0, 
                //swap(A[0], A[i])
				temp = A[1];
				A[1] = A[i];
				A[i] = temp;
			, 
                //swap(A[c[i]], A[i])
				temp = A[c[i]];
				a[c[i]] = a[i];
				a[i] = temp;
			);
			Print( A );
            //Swap has occurred ending the for-loop. Simulate the increment of the for-loop counter
			c[i] = c[i] + 1; 
            //Simulate recursive call reaching the base case by bringing the pointer to the base case analog in the array
			i = 1;
		, 
        //else
			//Calling generate(i+1, A) has ended as the for-loop terminated. Reset the state and simulate popping the stack by incrementing the pointer.
			c[i] = 1;
			i = i + 1;
		)
	);
);

Craige_Hales

// Heap's algorithm from https://en.wikipedia.org/wiki/Heap%27s_algorithm
// note: the above uses 0-based arrays, JMP uses 1-based. The above also 
// must be using call-by-reference and JMP uses call-by-value. below uses
// a global array A rather than trying to find a way to pass the array by
// reference. For similar reasons, swap(x,y) is expanded in-line.

generate = Function( {k},
	{i, temp},
	If( k == 1,
		Write( "\!n", A );//
	, //else
		// Generate permutations with kth unaltered
		// Initially k == length(A)
		generate( k - 1 );
        // Generate permutations for kth swapped with each k-1 initial
		For( i = 0, i < k - 1, i += 1, 
            // Swap choice dependent on parity of k (even or odd)
			If( Mod( k, 2 ) == 0,
				temp = A[i + 1];
				A[i + 1] = A[k];
				A[k] = temp;
			, //else
				temp = A[1];
				A[1] = A[k];
				A[k] = temp;
			);
			generate( k - 1 );
		);
	)
);

A = [1 2];
generate( N Cols( A ) );

A = {"a", "b", "c"};
generate( N Items( A ) );

A = 1 :: 4;
generate( N Cols( A ) );

[1 2]
[2 1]
{"a", "b", "c"}
{"b", "a", "c"}
{"c", "a", "b"}
{"a", "c", "b"}
{"b", "c", "a"}
{"c", "b", "a"}
[1 2 3 4]
[2 1 3 4]
[3 1 2 4]
[1 3 2 4]
[2 3 1 4]
[3 2 1 4]
[4 2 1 3]
[2 4 1 3]
[1 4 2 3]
[4 1 2 3]
[2 1 4 3]
[1 2 4 3]
[1 3 4 2]
[3 1 4 2]
[4 1 3 2]
[1 4 3 2]
[3 4 1 2]
[4 3 1 2]
[4 3 2 1]
[3 4 2 1]
[2 4 3 1]
[4 2 3 1]
[3 2 4 1]
[2 3 4 1]

thanks for making me revisit the wikipedia version! Last time I just found a different variation that was easier to convert.

All comments

txnelson

I converted the non recursive form of the code to JMP. See if this helps

generate = Function( {n, A}, 
    //c is an encoding of the stack state. c[k] encodes the for-loop counter for when generate(k+1, A) is called
	
	c = {};

	For( i = 1, i <= n, i++, c[i] = 1 );
	Print( A );
    
    //i acts similarly to the stack pointer
	i = 1;
	While( i <= n,
		If( c[i] < i,
			If( Mod( i, 2 ) == 0, 
                //swap(A[0], A[i])
				temp = A[1];
				A[1] = A[i];
				A[i] = temp;
			, 
                //swap(A[c[i]], A[i])
				temp = A[c[i]];
				a[c[i]] = a[i];
				a[i] = temp;
			);
			Print( A );
            //Swap has occurred ending the for-loop. Simulate the increment of the for-loop counter
			c[i] = c[i] + 1; 
            //Simulate recursive call reaching the base case by bringing the pointer to the base case analog in the array
			i = 1;
		, 
        //else
			//Calling generate(i+1, A) has ended as the for-loop terminated. Reset the state and simulate popping the stack by incrementing the pointer.
			c[i] = 1;
			i = i + 1;
		)
	);
);

Craige_Hales

// Heap's algorithm from https://en.wikipedia.org/wiki/Heap%27s_algorithm
// note: the above uses 0-based arrays, JMP uses 1-based. The above also 
// must be using call-by-reference and JMP uses call-by-value. below uses
// a global array A rather than trying to find a way to pass the array by
// reference. For similar reasons, swap(x,y) is expanded in-line.

generate = Function( {k},
	{i, temp},
	If( k == 1,
		Write( "\!n", A );//
	, //else
		// Generate permutations with kth unaltered
		// Initially k == length(A)
		generate( k - 1 );
        // Generate permutations for kth swapped with each k-1 initial
		For( i = 0, i < k - 1, i += 1, 
            // Swap choice dependent on parity of k (even or odd)
			If( Mod( k, 2 ) == 0,
				temp = A[i + 1];
				A[i + 1] = A[k];
				A[k] = temp;
			, //else
				temp = A[1];
				A[1] = A[k];
				A[k] = temp;
			);
			generate( k - 1 );
		);
	)
);

A = [1 2];
generate( N Cols( A ) );

A = {"a", "b", "c"};
generate( N Items( A ) );

A = 1 :: 4;
generate( N Cols( A ) );

thanks for making me revisit the wikipedia version! Last time I just found a different variation that was easier to convert.

Craige_Hales

2nd half of your question, how to not store the whole list?

Great question; I believe the only answer JMP offers is to make your code be called from where JIM's solution does a print() or my solution does a write(). If JMP offered a generator or co-routines @XanGregg , you could have a more flexible solution where your code could ask the generator for the next sequence from the point (or points) where you need one. Listing them out into a table ahead of time might be the best choice if you need that.

Are you free to share more details about the project? The time required to look at all of 14! or 15! permutations is probably prohibitive. If you expect to find a good-enough answer before looking at all the permutations, maybe using random permutations, maybe with an annealing algorithm, might be a better choice.

MathStatChem

Thanks for the code, both of you, it was helpful. Recursion always makes my head hurt, and it looks like JSL doesn't easily allow you to do recursion in a way that allows for assigning the output of the sequence of permutations to a list or matrix.

After using the generator functions, I realized that what I wanted to do would take too much computational time.

Here is the problem: There is a measure of efficacy used for vaccines that may not prevent but reduce the severity of a disease called mitigated fraction (MF). It is described here. It is based on the Wilcoxson Rank-Sum test statistic (W) for the comparison of two groups. So what I was wanting to do was to list out all the possible values of W (using all possible permutations of ranks) for two groups with given sample sizes, and then get from that all the possible values of MF. What I really wanted to show was that the criteria that we are using for MF to demonstrate efficacy equated to a critical value for the distribution of W under the null hypothesis that the distribution for both groups is the same.

The way I solved my problem was to assume an underlying distribution for each group and do a simulation study to get a distribution of MF under those assumptions. (Also, for larger sample sizes, W is asymptotically normal under H0: (no difference in populations), so that is also another way to solve part of the problem). Using simulation though allowed me to also examine the power under different alternative hypothesis, which made my analysis more complete.

johnmoore

Here is a function I created based on Craige's script.

</CODE></PRE><PRE><CODE class="">Names Default To Here( 1 );
Clear Log();

permutate = Function( {list},
	per = New Namespace();
	per:swap = Function( {targetList, firstPosition, secondPosition}, //returns a list with elements in firstPosition and secondPosition swapped
		{temp},
		temp = targetList[firstPosition];
		targetList[firstPosition] = targetList[secondPosition];
		targetList[secondPosition] = temp;
		Return( targetList );
	);
	per:generate = Function( {k},
		{i, temp},
		If( k == 1,
			Insert Into( per:result, Eval List( List( per:A ) ) ), //else
			per:generate( k - 1 );
        // Generate permutations for kth swapped with each k-1 initial
			For( i = 0, i < k - 1, i += 1, 
            // Swap choice dependent on parity of k (even or odd)
				If( Mod( k, 2 ) == 0,
					per:A = per:swap( per:A, k, i + 1 ), //else
					per:A = per:swap( per:A, 1, k )
				);
				per:generate( k - 1 );
			);
		)
	);
	per:result = {};
	per:A = list;
	per:generate( N Items( per:A ) );
	result = per:result;
	Delete Namespaces( per );
	Return( result );
);



A = {"a", "b", "c", "d"};
permutate( A );