Algorithme pour obtenir toutes les combinaisons de taille n à partir d'un tableau (Java)? [fermé]
En ce moment, j'essaie d'écrire une fonction qui prend un tableau et un entier n, et donne une liste de chaque combinaison de taille n (donc une liste de tableaux int). Je suis capable de l'écrire en utilisant n boucles imbriquées, mais cela ne fonctionne que pour une taille spécifique de sous-ensemble. Je ne peux pas comprendre comment généraliser à n'importe quelle taille de combinaison. Je pense que je dois utiliser la récursivité?
C'est le code pour toutes les combinaisons de 3 éléments, et j'ai besoin d'un algorithme pour un certain nombre d'éléments.
import java.util.List;
import java.util.ArrayList;
public class combinatorics{
public static void main(String[] args) {
List<int[]> list = new ArrayList<int[]>();
int[] arr = {1,2,3,4,5};
combinations3(arr,list);
listToString(list);
}
static void combinations3(int[] arr, List<int[]> list){
for(int i = 0; i<arr.length-2; i++)
for(int j = i+1; j<arr.length-1; j++)
for(int k = j+1; k<arr.length; k++)
list.add(new int[]{arr[i],arr[j],arr[k]});
}
private static void listToString(List<int[]> list){
for(int i = 0; i<list.size(); i++){ //iterate through list
for(int j : list.get(i)){ //iterate through array
System.out.printf("%d ",j);
}
System.out.print("n");
}
}
}
3 réponses
C'est un problème bien étudié de générer tous les K-sous-ensembles, ou K-combinaisons, ce qui peut être facilement fait sans récursivité.
, L'idée est d'avoir le tableau de taille k gardant séquence de indices d'éléments du tableau d'entrée (qui sont des nombres à partir de 0 à n - 1) dans l'ordre croissant. ( le sous-ensemble peut alors être créé en prenant des éléments par ces indices à partir du tableau initial.) Nous devons donc générer toutes ces séquences d'index.
Premier la séquence d'index sera [0, 1, 2, ... , k - 1], à la deuxième étape, elle passe à [0, 1, 2,..., k], puis à [0, 1, 2, ... k + 1] et ainsi de suite. La dernière séquence sera [n - k, n - k + 1, ..., n - 1].
À chaque étape, l'algorithme recherche le plus proche de l'élément final qui peut être incrémenté, l'incrémente et remplit les éléments directement à cet élément.
Pour illustrer, considérons n = 7 et k = 3. La première séquence d'index est [0, 1, 2], puis [0, 1, 3] et ainsi de suite... À un moment donné, nous avons [0, 5, 6]:
[0, 5, 6] <-- scan from the end: "6" cannot be incremented, "5" also, but "0" can be
[1, ?, ?] <-- "0" -> "1"
[1, 2, 3] <-- fill up remaining elements
next iteration:
[1, 2, 3] <-- "3" can be incremented
[1, 2, 4] <-- "3" -> "4"
Ainsi, [0, 5, 6] est suivi de [1, 2, 3], puis va [1, 2, 4] etc.
Code:
int[] input = {10, 20, 30, 40, 50}; // input array
int k = 3; // sequence length
List<int[]> subsets = new ArrayList<>();
int[] s = new int[k]; // here we'll keep indices
// pointing to elements in input array
if (k <= input.length) {
// first index sequence: 0, 1, 2, ...
for (int i = 0; (s[i] = i) < k - 1; i++);
subsets.add(getSubset(input, s));
for(;;) {
int i;
// find position of item that can be incremented
for (i = k - 1; i >= 0 && s[i] == input.length - k + i; i--);
if (i < 0) {
break;
}
s[i]++; // increment this item
for (++i; i < k; i++) { // fill up remaining items
s[i] = s[i - 1] + 1;
}
subsets.add(getSubset(input, s));
}
}
// generate actual subset by index sequence
int[] getSubset(int[] input, int[] subset) {
int[] result = new int[subset.length];
for (int i = 0; i < subset.length; i++)
result[i] = input[subset[i]];
return result;
}
Si j'ai bien compris votre problème, Cet article semble indiquer ce que vous essayez de faire.
Pour citer l'article:
Méthode 1 (Correction des éléments et répétition)
Nous créons un tableau temporaire 'data []' qui stocke toutes les sorties une par un. L'idée est de commencer à partir du premier index (index = 0) dans data [], un par un fixer les éléments à cet index et se reproduire pour les index restants. Laisser le tableau d'entrée soit {1, 2, 3, 4, 5} et R être 3. Nous premier correctif 1 à l'index 0 dans data [], puis réapparaître pour les index restants, puis nous fixons 2 à l'index 0 et réapparaître. Enfin, nous corrigeons 3 et réapparaissons pour les index restants. Lorsque nombre d'éléments dans les données [] devient égal à r (taille de a combinaison), Nous imprimons des données[].
Méthode 2 (inclure et exclure chaque élément)
Comme la méthode ci-dessus, Nous créons un tableau temporaire de données[]. Idée voici similaire au problème de somme de sous-ensemble. Nous considérons un par un chaque élément de tableau d'entrée, et récur pour deux cas:
- L'élément est inclus dans la combinaison actuelle (nous mettons l'élément dans data[] et incrémentons l'index disponible suivant dans data [])
- l'élément est exclu dans la combinaison actuelle (nous ne mettons pas l'élément et ne changeons pas l'index)
Lorsque le nombre d'éléments dans les données[] devient égal à r (taille de a combinaison), nous l'imprimons.
Vous pouvez certainement le faire avec l'itération.
Voici une solution qui calcule le nombre de tableaux que nous devrions créer, puis les Construit en utilisant math pour calculer quel élément du tableau source devrait être à quel endroit:
public static void combinations(int n, int[] arr, List<int[]> list) {
// Calculate the number of arrays we should create
int numArrays = (int)Math.pow(arr.length, n);
// Create each array
for(int i = 0; i < numArrays; i++) {
int[] current = new int[n];
// Calculate the correct item for each position in the array
for(int j = 0; j < n; j++) {
// This is the period with which this position changes, i.e.
// a period of 5 means the value changes every 5th array
int period = (int) Math.pow(arr.length, n - j - 1);
// Get the correct item and set it
int index = i / period % arr.length;
current[j] = arr[index];
}
list.add(current);
}
}
Mise à Jour:
Voici une version optimisée qui réduit considérablement le nombre d'appels vers Math.pow
public static void combinations(int n, int[] arr, List<int[]> list) {
// Calculate the number of arrays we should create
int numArrays = (int)Math.pow(arr.length, n);
// Create each array
for(int i = 0; i < numArrays; i++) {
list.add(new int[n]);
}
// Fill up the arrays
for(int j = 0; j < n; j++) {
// This is the period with which this position changes, i.e.
// a period of 5 means the value changes every 5th array
int period = (int) Math.pow(arr.length, n - j - 1);
for(int i = 0; i < numArrays; i++) {
int[] current = list.get(i);
// Get the correct item and set it
int index = i / period % arr.length;
current[j] = arr[index];
}
}
}