keb2308
Goto Top

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 = 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);
	}

}

Content-Key: 301834

Url: https://administrator.de/contentid/301834

Printed on: April 18, 2024 at 00:04 o'clock