«

Hi all!

I have an array of instances from which I would like to produce all
possible permutations concerning the order as quickly as possible.
Before I go and implement that manually, maybe anyone has a hint for me
how this might be handled "best".

array = 1 2 3

permutations = array.length! (faculty)

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Is there a trick of how do do it quickly?

Karsten

Karsten Wutzke wrote:
> Is there a trick of how do do it quickly?

Did you just ask how to generate permutations quickly?

All permutations?

Are you sure you understand what you're asking?

There are n! permutations of an n-element array. There is NO quick way
to generate every element of the list. The list is huge. The best you
can hope for (asymptotically) is linear in the size of the output. And
just about every algorithm does that. Reducing the amount of time taken
by just about any constant factor means nothing compared to the
additional time it takes to generate all the permutations of a very
slightly larger list.

If the speed does matter all that much, show us the code you're using
(or considering using). If there's anything horribly inefficient with
it, we'll let you know. But there probably won't be anything
significantly inefficient with any algorithm you can think of.

Carl Howells wrote:

> Karsten Wutzke wrote:
>
>> Is there a trick of how do do it quickly?
>
>
> Did you just ask how to generate permutations quickly?
>

Yes. The array contains references to objects, these objects don't have
to be deep copied. Generating permutations of references is perfect.

> All permutations?

Yes, at least for now. If it is too slow, I'll have to begin thinking
about reducing the number of relevant permutations, but that is another
story.

>
> Are you sure you understand what you're asking?
>

Yes. I know n! can get very high quickly, but I'm thinking about upper
borders of 4-6, maybe more if the "permutation generator" is efficient
enough.

> There are n! permutations of an n-element array. There is NO quick way
> to generate every element of the list. The list is huge. The best you
> can hope for (asymptotically) is linear in the size of the output. And
> just about every algorithm does that. Reducing the amount of time taken
> by just about any constant factor means nothing compared to the
> additional time it takes to generate all the permutations of a very
> slightly larger list.
>

Sure. This is where my upper border considerations come in. I can adjust
as needed, but it must not be less than ~4. I don't expect it to be
larger than ~7.

> If the speed does matter all that much, show us the code you're using
> (or considering using).

Hmm. Can't offer any code yet. Right now, I'm using the same array *as
is* for testing purposes (could be considered). Sounds strange? Maybe.
Don't ask for the semantics. I'm really just looking for an efficient
permutations generator. But I haven't thought of an algo yet. Currently
there are more important things to attend. I just wanted to ask, if
there was some kind of standard way/code listing which I could adopt for
my purpose.

If there's anything horribly inefficient with
> it, we'll let you know. But there probably won't be anything
> significantly inefficient with any algorithm you can think of.

Karsten

On Wed, 03 Mar 2004 00:28:41 +0100, Karsten Wutzke
<kwutzke-> wrote or quoted :

>I have an array of instances from which I would like to produce all
>possible permutations concerning the order as quickly as possible.

http://mindprod.com/jgloss/permutation.html

--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.

Karsten Wutzke <kwutzke-> wrote in message news:<c235ba$pov$03$>...
> Hi all!
>
> I have an array of instances from which I would like to produce all
> possible permutations concerning the order as quickly as possible.
> Before I go and implement that manually, maybe anyone has a hint for me
> how this might be handled "best".

I came up with the following algorithm. Don't know if it's the best
method, but it's quite easy to understand and is fairly quick. It uses
recursion.

public class Test {
private static int[] input;
private static int outputIndex;
private static int[][] output;

private static void permutations(int offset) {
if (input.length - offset == 1) {
// Input now contains a permutation, here I store it in output,
// but you can do anything you like with it
output[outputIndex] = new int[input.length];
System.arraycopy(input, 0, output[outputIndex++], 0,
input.length);
return;
}

int a = input[offset];

for (int i=offset; i<input.length; i++) {
// Swap elements
int b = input[i];
input[i] = a;
input[offset] = b;

permutations(offset + 1);

// Restore element
input[i] = b;
}

input[offset] = a;
}

private static int faculty(int n) {
return n == 1 ? n : n * faculty(n - 1);
}

public static void main(String[] args) throws Exception {
input = new int[]{1, 2, 3, 4, 5, 6};
output = new int[faculty(input.length)][];
permutations(0);

for (int i=0; i<output.length; i++) {
for (int j=0; j<output[i].length; j++)
System.out.print((j > 0 ? ", " : "") + output[i][j]);

System.out.println();
}
}
}

/Jesper Nordenberg

> I have an array of instances from which I would like to produce all
> possible permutations concerning the order as quickly as possible.
> Before I go and implement that manually, maybe anyone has a hint for me
> how this might be handled "best".

Below is some code that does it. There is a method for an int array and one
for a char array. As long as your objects implement the Comparable
interface (i.e., they have a compareTo method), you can easily adapt this
code by replacing things like

while (a[j] > a[k]) { ... }

with

while (a[j].compareTo(a[k]) > 0) { ... }

If your objects don't implement Comparable (and they have no natural
ordering), you can just arbitrarily assign them unique numbers and permute
them based on these numbers.

------------------- here's the code -------------------


import java.util.*;

// Permutation utility class. has nextPerm() methods for
// a char[], and int[].
// Adapted from Kenneth Rosen's discrete math book for programming contests.

public class Permutations {

public static int[] nextPerm(int[] arr) {
int[] a = (int[]) arr.clone();
int n = a.length-1;
int j = n - 1;
// "123, 132, 213, 231, 312, 321"
while (a[j] > a[j+1]) {
if (j==0) {
// last permutation - reset
int[] error = new int[] { 0 } ;
return error;
}
j--;
}

// j is the largest subscript with a[j] < a[j+1]
int k = n;
while (a[j] > a[k]) {
// sanity checking here
k--;
}
// a[k] is the smallest term greater than a[j] to the
// right of a[j] -- swap a[j] and a[k]
int tmp = a[j]; a[j] = a[k]; a[k] = tmp;
int r = n;
int s = j + 1;

while (r > s) {
// swap a[r] and a[s]
tmp = a[r];
a[r] = a[s];
a[s] = tmp;
r--;
s++;
}

return a;
}
public char[] nextPerm(char[] arr) {
char[] a = (char[]) arr.clone();
int n = a.length-1;
int j = n - 1;
// "123, 132, 213, 231, 312, 321"
while (a[j] > a[j+1]) {
if (j==0) {
// last permutation - reset
char[] error = new char[] { 0 } ;
return error;
}
j--;
}

// j is the largest subscript with a[j] < a[j+1]
int k = n;
while (a[j] > a[k]) {
// sanity checking here
k--;
}
// a[k] is the smallest term greater than a[j] to the
// right of a[j] -- swap a[j] and a[k]
char tmp = a[j]; a[j] = a[k]; a[k] = tmp;
int r = n;
int s = j + 1;

while (r > s) {
// swap a[r] and a[s]
tmp = a[r];
a[r] = a[s];
a[s] = tmp;
r--;
s++;
}

return a;
}

// factorial
public long fact(int n) {
int f = 1;
for (int i=1; i <= n; i++)
f *= i;
return f;
}

public static void main(String[] args) {
// test char array
char[] sc = "123456".toCharArray();
long n = p.fact(sc.length);
long start = System.currentTimeMillis();
System.out.println("char array Time = "+start);
System.out.println("Fact = "+n);
for (long i=0; i < n; i++) {
//System.out.println("sc = "+new String(sc));
sc = p.nextPerm(sc);
}
long end = System.currentTimeMillis();
System.out.println("Time = "+end+" -- elapsed = "+""+(end-start));


int[] ar = { 0,1,2,3 };
n = p.fact(ar.length);
for (long i=0; i < n; i++) {
System.out.print("ar = ");
for (int j=0; j < ar.length; j++)
System.out.print(ar[j]+", ");
System.out.println();
ar = p.nextPerm(ar);
}
}
}