Methode um alle Kombinationen eines (int-)Arrays zu bestimmen - Optimierungsmöglichkeiten?
Hallo,
ich brauch eine Methode die einen Array als parameter nimmt und dann ein Array von Arrays aller Kombinationsmöglichkeiten (mit n Objekten) zurückgibt.
Also nCr.
zb.:
Parameter int = {0,1,2}
Returns int =
Das funktioniert soweit, nur leider ist meine Methode viel zu langsam. Für 48C4 (=194580 Kombinatinen, braucht bei mir 182000ms) gets grad so noch, aber ich brauchs für 48C5... Kann mir jemand weiterhelfen?
Danke!
Hier ist mein Code zum testen.
ich brauch eine Methode die einen Array als parameter nimmt und dann ein Array von Arrays aller Kombinationsmöglichkeiten (mit n Objekten) zurückgibt.
Also nCr.
zb.:
Parameter int = {0,1,2}
Returns int =
0,0},{0,1}, {1,0},{1,1},{0,2},{2,0},{2,2},{1,2},{2,1
Das funktioniert soweit, nur leider ist meine Methode viel zu langsam. Für 48C4 (=194580 Kombinatinen, braucht bei mir 182000ms) gets grad so noch, aber ich brauchs für 48C5... Kann mir jemand weiterhelfen?
Danke!
Hier ist mein Code zum testen.
import java.util.Random;
import org.apache.commons.math3.util.CombinatoricsUtils;
public class Testclass {
public static Testclass testclass = new Testclass();
public int getTheSubsets = new int[48];
Random random = new Random();
public Testclass(){
for(int i=0;i<getTheSubsets.length;i++){
getTheSubsets[i]=random.nextInt(100000000);
}
}
public static int getSubsetCombinations(final int pNumberOfCards, int... pComCards) {
long startTime = System.nanoTime();
int length = pComCards.length;
Double POSSIBLECOMBINATIONSDOUBLE = getNumberOfPossibleCombinations(length, pNumberOfCards);
int POSSIBLECOMBINATIONS = POSSIBLECOMBINATIONSDOUBLE.intValue();
int result = new int[POSSIBLECOMBINATIONS][pNumberOfCards];
for (int i = 0; i < pNumberOfCards; i++) {
result[i] = new int[pNumberOfCards];
}
int indexesOfSubset = new int[pNumberOfCards]; // here we'll keep
// indices
// pointing to elements in input array
if (pNumberOfCards <= length) {
// first index sequence: 0, 1, 2, ...
for (int i = 0; (indexesOfSubset[i] = i) < pNumberOfCards - 1; i++)
;
result = (getSubset(pNumberOfCards, pComCards, indexesOfSubset));
for (;;) {
int i;
// find position of item that can be incremented
for (i = pNumberOfCards - 1; i >= 0 && indexesOfSubset[i] == length - pNumberOfCards + i; i--)
;
if (i < 0) {
break;
} else {
indexesOfSubset[i]++; // increment this item
for (++i; i < pNumberOfCards; i++) { // fill up remaining
// items
indexesOfSubset[i] = indexesOfSubset[i - 1] + 1;
}
for (int j = 0; j < POSSIBLECOMBINATIONS; j++) {
// pComCards isn't allowed to contain 0
// -> if result[j] == 0, then subset has not been set
if (result[j] == 0) {
result[j] = getSubset(pNumberOfCards, pComCards, indexesOfSubset);
break;
}
}
}
}
}
long endTime = System.nanoTime();
long duration = (endTime - startTime);
System.out.println("Time to run getSubsetCombinations: "+duration/1000000);
return result;
}
// generate actual subset by index sequence
private static int getSubset(int pNumberOfCards, int input, int subset) {
int result = new int[pNumberOfCards];
for (int i = 0; i < pNumberOfCards; i++) {
result[i] = input[subset[i]];
}
return result;
}
// how many combination possibilities are there?
public static double getNumberOfPossibleCombinations(final int toChooseFrom, final int howMany) {
double a = CombinatoricsUtils.factorialDouble(toChooseFrom);
double b = CombinatoricsUtils.factorialDouble(howMany);
double c = CombinatoricsUtils.factorialDouble(toChooseFrom - howMany);
return a / (b * c);
}
public static void main(String args) {
Testclass.getSubsetCombinations(4, Testclass.testclass.getTheSubsets);
}
}
Please also mark the comments that contributed to the solution of the article
Content-Key: 301834
Url: https://administrator.de/contentid/301834
Printed on: April 24, 2024 at 20:04 o'clock