finden Sie alle Kombinationen von gegebenen Zahlen in einer bestimmten Array-Größe

Question

Ich muss alle Kombinationen aus der Größe n, die aus den Zahlen in Zahlen Array besteht zu finden. Ich habe versucht, es mit der Funktion zu tun, die ich unten geschrieben habe, aber es braucht viel Zeit und Speicher, um es so zu machen.

Gibt es eine Möglichkeit, es effizienter zu machen?

void createCombinationArray(ArrayList<Integer> numbers, int n, ArrayList<Integer> start) { 
    if (start.size() >= n) { 
     monthsComb.add(new ArrayList<>(start)); 
    } else { 
     for (Integer x : numbers) { 
      start.add(x); 
      createCombinationArray(numbers, n, start); 
      start.remove(start.lastIndexOf(x)); 
     } 
    } 
} 

Answer 1

Fragen Sie sich, ob Sie wirklich alle diese Listen im Voraus generieren müssen. Vielleicht wäre es akzeptabel, sie auf Anfrage zu generieren.

Beachten Sie, dass jede dieser Listen durch eine Zahl mit numbers.length Bits, n oder mehr davon dargestellt werden kann. Sie könnten mit einer Datenstruktur dieser Art arbeiten, um auf eine externe Liste zu verweisen.

Es wäre ziemlich einfach, eine List-Implementierung mit diesem Verhalten zu schreiben.

import java.util.BitSet; 
import java.util.List; 

public class SelectiveList<T> implements List<T> { 
    private final BitSet bitSet; 
    private final List<T> list; 

    public SelectiveList(BitSet bitSet, List<T> list) { 
     this.bitSet = bitSet; 
     this.list = list; 
    } 

    @Override 
    public T get(int index) { 
     return list.get(nthOnBit(index)); 
    } 

    private int nthOnBit(int n) { 
     int onBits = 0; 
     int i; 
     for (i = bitSet.nextSetBit(0); i >= 0 && onBits < n; i = bitSet.nextSetBit(i + 1)) { 
      onBits++; 
     } 
     if (onBits < n) { 
      throw new IllegalArgumentException(); 
     } 

     return i; 
    } 

    // etc. 
} 

Answer 2

Eine Möglichkeit, es zu tun efficently (sowohl für die Zeit und Speicher) ist das Ergebnis als int[][] statt Collection<List<Integer>> zu speichern (was ich nehme an, die Art des monthsComb Feldes zu sein). Sie können dies tun, weil Sie wissen, dass, wenn Sie k Zahlen haben, das Ergebnis Binomial(n, k) Kombinationen von n Zahlen sein wird.

Eine andere Möglichkeit (wie @ Phia-CM vorgeschlagen) wäre, eine nicht rekursive Version des Algorithmus zu implementieren.

Ich weiß, sie sind beide unruhig zu implementieren, aber das ist der Weg für die Effizienz.

Answer 3

können Sie dies versuchen:

package combination; 

import java.math.BigInteger; 
import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.Iterator; 
import java.util.List; 

public class Combination implements Iterator<List<Integer>> { 

    public Combination(final List<Integer> numbers, final int n) { 
     this.numbers = numbers; 
     this.n = n; 
     this.current = BigInteger.valueOf(0); 
     this.radix = BigInteger.valueOf(numbers.size()); 
     this.size = this.radix.pow(n); 
    } 

    @Override 
    public final boolean hasNext() { 
     return this.current.compareTo(size) < 0; 
    } 

    @Override 
    public final List<Integer> next() { 
     List<Integer> result = new ArrayList(this.n); 
     BigInteger value = this.current; 
     for(int i=0; i<n; i++) { 
      result.add(i, this.numbers.get(
        value.mod(this.radix).intValueExact())); 
      value = value.divide(this.radix); 
     } 
     this.current = this.current.add(BigInteger.valueOf(1)); 
     return result; 
    } 

    private final List<Integer> numbers; 
    private final int n; 
    private BigInteger current; 
    private final BigInteger size; 
    private final BigInteger radix; 

    public static void main(String[] args) { 
     Combination cb = new Combination(Arrays.asList(0, 2, 4, 6), 3); 
     while (cb.hasNext()) { 
      System.out.println(cb.next()); 
     } 
    } 
}