Distributing permutations / java

Martyr

Hi, i need to optimise this code.
specifically, i'm looking for a formula, if one exists.i could only upload a text file, just rename it to DistPerm.java
some values are hardcoded also.

/*
        permutation distribution

        given a minimum length to begin with, a maximum length to end, and an index length
        create all permutations.

        then distribute them evenly across one or more cpus, beginning/ending at correct point
        
        uses very in-efficient algorithm.
        the main bottleneck is in the while() loop where it decreases by charlen in first, and by 1 in second.
        thought about decreasing by (charlen^2) but there must a formula for doing these kind of calculations
        quicker, in one loop.

*/
import java.util.*;
import java.math.*;

public class DistPerm {
	
        public static void sop(String s) {
               System.out.print(s);
        }

        public static void main(String []args) {

               int indexLen = 26;
               int array[] = new int[26+1];

               int minLen = 1;
               int maxLen = 4;
               int cpus = 2;

               double totalPermutations=0.0;
               double remainder=0.0;

               int cpuPermutations[] = new int[20];

               int i,j;
		
               // calculate the total number of permutations possible

            //if(args.length == 3) {
            //   minLen   = arg[1];
            //   maxLen   = arg[2];
            //   indexLen = arg[3];
            //   cpus     = arg[4];
            //

               for(i=minLen;i<=maxLen;i++)
                   totalPermutations += Math.pow((double)indexLen,(double)i);
			
               sop("\nTotal number of permutations = "+(int)totalPermutations+"\n\n");

               // split keyspace into distributed permutations based on
               // number of cpus available

               remainder = (totalPermutations % cpus);
               totalPermutations -= remainder;

               for(i=0;i<cpus;i++) {
                   cpuPermutations[i] = (int)(totalPermutations / cpus);
                   sop("permutations for cpu "+(i+1)+" = "+cpuPermutations[i]+"\n");
               }

               cpuPermutations[cpus-1]+=remainder;

               for(i=0;i<cpus;i++) {	                         // for number of cpus available

                   while(cpuPermutations[i] > indexLen) {        // while permutations > index length
                        array[1]++;                              // increase 2nd index

                        if(array[1] > indexLen) {                // if 2nd exceeds indexLen
                           array[1] = 1;                         // reset
                           array[2]++;                           // update 3rd

                           for(j=2;j<maxLen;j++) {               // then check all others for maxLen

                              if(array[j] > indexLen) {
                                 array[j] = 1;
                                 array[j+1]++;
                              }
                           }
                        }
                        cpuPermutations[i] -= indexLen;           // decrease by indexLen
                   }

                   while(cpuPermutations[i] > 0) {	          // while permutations > 0
                        array[0]++;

                        if(array[0] > indexLen) {
                           array[0] = 1;
                           array[1]++;

                           for(j=1;j<maxLen;j++) {

                               if(array[j] > indexLen) {
                                  array[j] = 1;
                                  array[j+1]++;
                               }
                           }
                        }
                        cpuPermutations[i]--;
                    }

                    System.out.print("\nArray index "+(i+1)+" ending:");

                    for(int a=0;a<maxLen;a++)
                        System.out.print(" "+(int)array[a]);
                }

                System.out.println();
            }
}

Total number of permutations = 475254

permutations for cpu 1 = 237627
permutations for cpu 2 = 237627

Array index 1 ending: 13 13 13 13
Array index 2 ending: 26 26 26 26

Mutant_Fruit

What exactly are you trying to accomplish? Explain it in english

Martyr

What exactly are you trying to accomplish? Explain it in english

my english just wouldn't be the best, i'm irish.

given a minimum length to begin with, a maximum length to end, and an index length which should not be exceeded, create all permutations.

permutations.. create all possible combinations for a given length using a set of elements.
better to think of the array as holding the index of a character set

say the set/string is "0123456789"
forget about the fact that zero would be "0" in this string, think of array[1] as holding "0"

for all possible permutations of 1 - 4 in length using the string, of length 10, its calculated as.

(10 ^ 1) + (10 ^ 2) + (10 ^ 3) + (10 ^ 4) = 11110 total combinations.

now, if you have 2 computers to calculate these permutations, distribute them evenly across these.

total combinations / number of cpus available
11110 / 2 = 5555 permutations each

computer 1 gets array index of 0,0,0,0 ending at 5,5,5,5
computer 2 gets array index of 6,5,5,5 ending at 9,9,9,9

and so on..if more than 2 computers, or greater length.

so, how to figure out where each array index begins and ends is the problem..sorry if i can't explain it well, but i think you should know what i'm talking about.

Hobbes

If you have an array index of 0,0,0,0,0 ending at 5,5,5,5,5 then the total permutations 55556 ? Or am I missing something?

if you are referring to the permutation of objects (not numbers) then my guess is you only need to work out half of the permutations as the other half will be a mirror of the first lot?

Mutant_Fruit

Do you want to create each of the permutations or just find out how many their are?

If you want to create them, you should have 1 separate thread per CPU and then a main thread which will run a while loop dispatching blocks of data to be computed to each of the available worker threads.

The worker threads would then signal the main thread when they've finished computing their block of data.

For example if you have a range of digits from 1000 - 9999 you could make thread 1 do all permutations starting with 1, then thread 2 do all permutations starting with 2.

As soon as one of them is finished, tell them to do all permutations starting with 3 etc.

EDIT: Then you could pull some fancy tricks to avoid duplicating work, but that's a separate issue

Martyr

If you have an array index of 0,0,0,0,0 ending at 5,5,5,5,5 then the total permutations 55556 ? Or am I missing something?

i probably used a bad string as example, because its a little confusing.

say the string is "ABCDEF"
then the array index values of 5,5,2,5,1 would equal "EEBEA"

i'm using arrays to calculate where each permutation should begin and end when distributed across more than 1 cpu either on seperate machine or multi-core processor using subtraction.
if there is a better way (and i'm sure there must be) i would gladly use it instead.

say the options are

minLen = 1
maxLen = 3
cpus = 2
string length = 3 (doesn't matter what the string is, because the numbers are just an index of the string)

total combinations = (4^1) + (4^2) + (4^3) = 98?

98 / 2 = 49 combinations each

cpu 1 starts at 1 and ends at 49
cpu 2 starts at 50 and ends at 98

maybe there is no formula, as such..just a better way.

Do you want to create each of the permutations or just find out how many their are?

no, that is already known.
the issue is, when the TOTAL permutations is distributed, how do you know where each permutation should begin/end without computing the same permutation..?

the routine i wrote does this, but not efficiently.

EDIT: there is also loss of precision when casting from double to int when ALOT of permutations are to be calculated.

Capt'n Midnight

If I read it right you have N processors/cores/nodes/clustered zx81's Ok say 32
you have a character set that can have (say alphanumeric but no "i" or "o") 34 values
you have 7 characters

34^7 = 52,523,350,144 combinations

52,523,350,144 /32 = 1641354692

You could split the job over the 32 this way
The first would run 0-1641354691 then next 1641354692 ... and so on to ... 52,523,350,144

Or you could leave one in control and split the rest 31 ways - 1694301618 per unit.

you could store the characters in a 34 element array to covert from/to a number


PHP tags are prettier for code.
[php]
/*
permutation distribution

given a minimum length to begin with, a maximum length to end, and an index length
create all permutations.

then distribute them evenly across one or more cpus, beginning/ending at correct point

uses very in-efficient algorithm.
the main bottleneck is in the while() loop where it decreases by charlen in first, and by 1 in second.
thought about decreasing by (charlen^2) but there must a formula for doing these kind of calculations
quicker, in one loop.

*/
import java.util.*;
import java.math.*;

public class DistPerm {

public static void sop(String s) {
System.out.print(s);
}

public static void main(String []args) {

int indexLen = 26;
int array[] = new int[26+1];

int minLen = 1;
int maxLen = 4;
int cpus = 2;

double totalPermutations=0.0;
double remainder=0.0;

int cpuPermutations[] = new int[20];

int i,j;

// calculate the total number of permutations possible

//if(args.length == 3) {
// minLen = arg[1];
// maxLen = arg[2];
// indexLen = arg[3];
// cpus = arg[4];
//

for(i=minLen;i<=maxLen;i++)
totalPermutations += Math.pow((double)indexLen,(double)i);

sop("\nTotal number of permutations = "+(int)totalPermutations+"\n\n");

// split keyspace into distributed permutations based on
// number of cpus available

remainder = (totalPermutations % cpus);
totalPermutations -= remainder;

for(i=0;i<cpus;i++) {
cpuPermutations = (int)(totalPermutations / cpus);
sop("permutations for cpu "+(i+1)+" = "+cpuPermutations+"\n");
}

cpuPermutations[cpus-1]+=remainder;

for(i=0;i<cpus;i++) { // for number of cpus available

while(cpuPermutations > indexLen) { // while permutations > index length
array[1]++; // increase 2nd index

if(array[1] > indexLen) { // if 2nd exceeds indexLen
array[1] = 1; // reset
array[2]++; // update 3rd

for(j=2;j<maxLen;j++) { // then check all others for maxLen

if(array[j] > indexLen) {
array[j] = 1;
array[j+1]++;
}
}
}
cpuPermutations -= indexLen; // decrease by indexLen
}

while(cpuPermutations > 0) { // while permutations > 0
array[0]++;

if(array[0] > indexLen) {
array[0] = 1;
array[1]++;

for(j=1;j<maxLen;j++) {

if(array[j] > indexLen) {
array[j] = 1;
array[j+1]++;
}
}
}
cpuPermutations--;
}

System.out.print("\nArray index "+(i+1)+" ending:");

for(int a=0;a<maxLen;a++)
System.out.print(" "+(int)array[a]);
}

System.out.println();
}
}
[/php]

Martyr

[PHP]/*
permutation distribution (still not working)

Usage: ks <MIN> <MAX> <CHARS> <CPUS>

Examples:
********************************************
H:\>java DistPerm 1 4 0123456789 4

Number of processors:4
Minimum length:1
Maximum length:4
Characters:0123456789
Index Length:10

Total permutations = 11110.0

CPU 1:"0" -> "6661"
CPU 2:"7661" -> "3444"
CPU 3:"4444" -> "0227"
CPU 4:"1227" -> "9999"

********************************************
H:\>java DistPerm 1 7 ABCDEFGHIJKLMNOPQRSTUVWXYZ 4

Number of processors:4
Minimum length:1
Maximum length:7
Characters:ABCDEFGHIJKLMNOPQRSTUVWXYZ
Index Length:26

Total permutations = 8.353082582E9

CPU 1:"A" -> "SSSSSSF"
CPU 2:"TSSSSSF" -> "LMMMMMM"
CPU 3:"MMMMMMM" -> "EGGGGGT"
CPU 4:"FGGGGGT" -> "ZZZZZZZ"

********************************************

H:\>java DistPerm 1 7 ABCDEFGHIJKLMNOPQRSTUVWXYZ 8

Number of processors:8
Minimum length:1
Maximum length:7
Characters:ABCDEFGHIJKLMNOPQRSTUVWXYZ
Index Length:26

Total permutations = 8.353082582E9

CPU 1:"A" -> "VVVVVIC"
CPU 2:"WVVVVIC" -> "RSSSSSF"
CPU 3:"SSSSSSF" -> "NPPPPCJ"
CPU 4:"OPPPPCJ" -> "JMMMMMM"
CPU 5:"KMMMMMM" -> "FJJJJWP"
CPU 6:"GJJJJWP" -> "BGGGGGT"
CPU 7:"CGGGGGT" -> "XCDDDQW"
CPU 8:"YCDDDQW" -> "ZZZZZZZ"

*/
import java.util.*;
import java.math.*;

public class DistPerm {

public static void sop(String s) {
System.out.print(s);
}

public static void main(String []args) {

double totalPermutations=0.0;
double remainder=0.0;

int i,j;

if(args.length == 4) {

int minLen = Integer.parseInt(args[0]);
int maxLen = Integer.parseInt(args[1]);
String charset = args[2];
int cpus = Integer.parseInt(args[3]);
int indexLen = charset.length();
int array[] = new int[indexLen+1];

double cpuPermutations[] = new double[cpus];

// just a basic check of arguements.
if( (minLen==0) || (maxLen==0) || (minLen > maxLen) || (cpus==0) || (indexLen==0) ) {
sop("\n\tUsage: ks <MIN> <MAX> <CHARS> <CPUS>\n");
System.exit(10);
}

for(i=minLen;i<=maxLen;i++)
totalPermutations += Math.pow((double)indexLen,(double)i);

sop("\nNumber of processors:"+cpus+"\nMinimum length:"+minLen+"\nMaximum length:"+maxLen+"\nCharacters:"+charset+"\nIndex Length:"+charset.length()+"\n\nTotal permutations = "+totalPermutations+"\n");

// split keyspace into distributed permutations based on
// number of cpus available

remainder = (totalPermutations % cpus);
totalPermutations -= remainder;

for(i=0;i<cpus;i++) {
cpuPermutations = (totalPermutations / cpus);
//sop("permutations for cpu "+(i+1)+" = "+cpuPermutations+"\n");
}

cpuPermutations[cpus-1]+=remainder;

for(i=0;i<cpus;i++) { // for number of cpus available

sop("\nCPU "+(i+1)+":\"");

array[0]++;
cpuPermutations--;

for(int a=0;a<maxLen && array[a] != 0;a++)
sop(""+charset.charAt(array[a]-1));
sop("\"");

while(cpuPermutations > indexLen) { // while permutations > index length
array[1]++; // increase 2nd index

if(array[1] > indexLen) { // if 2nd exceeds indexLen
array[1] = 1; // reset
array[2]++; // update 3rd

for(j=2;j<maxLen;j++) { // then check all others for maxLen

if(array[j] > indexLen) {
array[j] = 1;
array[j+1]++;
}
}
}
cpuPermutations -= indexLen; // decrease by indexLen
}

while(cpuPermutations > 0) { // while permutations > 0
array[0]++;

if(array[0] > indexLen) {
array[0] = 1;
array[1]++;

for(j=1;j<maxLen;j++) {

if(array[j] > indexLen) {
array[j] = 1;
array[j+1]++;
}
}
}
cpuPermutations--;
}

//sop("\nArray index "+(i+1)+" ending:");

//for(int a=0;a<maxLen && array[a] != 0;a++)
// sop(" "+array[a]);

sop(" -> \"");

for(int a=0;a<maxLen && array[a] != 0;a++)
sop(""+charset.charAt( array[a]-1 ));

sop("\"");

} // end for
}
else {
sop("\n\tUsage: ks <MIN> <MAX> <CHARS> <CPUS>\n");
}
} // end main
}[/PHP]

yes, PHP tags do look better