combinaison sans répétition d'éléments N sans utiliser for..to..do
https://stackoverflow.com/questions/8316479
-
25-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
je veux charger dans une liste la combinaison du numéro N sans répétition, donnant à saisir les éléments et le groupe. Par exemple, avec 4 éléments [1,2,3,4], j'ai pour:
Group 1: [1][2][3][4];
Group 2: [1,2][1,3][1,4][2,3][2,4][3,4];
Group 3: [1,2,3][1,2,4][1,3,4][2,3,4]
Group 4: [1,2,3,4]
Maintenant, je l'ai résolu à l'aide de boucles imbriquées pour, par exemple avec le groupe 2, j'écris:
for x1 := 1 to 3 do
for x2 := Succ(x1) to 4 do
begin
// x1, x2 //
end
ou pour le groupe 3, je l'ai écrit:
for x1 := 1 to 2 do
for x2 := Succ(x1) to 3 do
for x3 := Succ(x2) to 4 do
begin
// x1, x2, x3 //
end
et ainsi pour les autres groupes. En général, si je veux le faire pour le groupe N, comme je peux le faire, sans procédures d'écriture de N avec boucles imbriquées? Je Pensé à une double boucle de while..do un à utiliser pour le compteur et un à utiliser pour les groupes comptent, mais il en est peu dur, je voulais savoir s'il y avait une solution plus simple et rapide, trop en utilisant booléen ou quelque chose opérateur si . Qui peut me donner suggérer une à ce sujet? Merci beaucoup.
La solution
Il semble que vous êtes à la recherche d'un algorithme rapide pour calculer tous les k-combinaisons. Le code Delphi suivant est une traduction directe du code C trouvé ici: Génération combinaisons . J'ai même fixé un bug dans le code!
program kCombinations;
{$APPTYPE CONSOLE}
// Prints out a combination like {1, 2}
procedure printc(const comb: array of Integer; k: Integer);
var
i: Integer;
begin
Write('{');
for i := 0 to k-1 do
begin
Write(comb[i]+1);
if i<k-1 then
Write(',');
end;
Writeln('}');
end;
(*
Generates the next combination of n elements as k after comb
comb => the previous combination ( use (0, 1, 2, ..., k) for first)
k => the size of the subsets to generate
n => the size of the original set
Returns: True if a valid combination was found, False otherwise
*)
function next_comb(var comb: array of Integer; k, n: Integer): Boolean;
var
i: Integer;
begin
i := k - 1;
inc(comb[i]);
while (i>0) and (comb[i]>=n-k+1+i) do
begin
dec(i);
inc(comb[i]);
end;
if comb[0]>n-k then// Combination (n-k, n-k+1, ..., n) reached
begin
// No more combinations can be generated
Result := False;
exit;
end;
// comb now looks like (..., x, n, n, n, ..., n).
// Turn it into (..., x, x + 1, x + 2, ...)
for i := i+1 to k-1 do
comb[i] := comb[i-1]+1;
Result := True;
end;
procedure Main;
const
n = 4;// The size of the set; for {1, 2, 3, 4} it's 4
k = 2;// The size of the subsets; for {1, 2}, {1, 3}, ... it's 2
var
i: Integer;
comb: array of Integer;
begin
SetLength(comb, k);// comb[i] is the index of the i-th element in the combination
//Setup comb for the initial combination
for i := 0 to k-1 do
comb[i] := i;
// Print the first combination
printc(comb, k);
// Generate and print all the other combinations
while next_comb(comb, k, n) do
printc(comb, k);
end;
begin
Main;
Readln;
end.
Sortie
{1,2}
{1,3}
{1,4}
{2,3}
{2,4}
{3,4}
Autres conseils
Voici une solution plutôt dépendante de plaisir sur bitsets. En l'état actuel, il est limité à des ensembles de taille ne dépasse pas 32. Je ne pense pas que ce soit une limitation pratique car il y a beaucoup de sous-ensembles pour un ensemble de plus de cardinalité que 32.
La sortie n'est pas dans l'ordre que vous voulez, mais ce serait assez facile à un recours si elle compte pour vous.
program VisitAllSubsetsDemo;
{$APPTYPE CONSOLE}
procedure PrintBitset(Bitset: Cardinal; Size: Integer);
var
i: Integer;
Mask: Cardinal;
SepNeeded: Boolean;
begin
SepNeeded := False;
Write('{');
for i := 1 to Size do begin
Mask := 1 shl (i-1);
if Bitset and Mask<>0 then begin
if SepNeeded then begin
Write(',');
end;
Write(i);
SepNeeded := True;
end;
end;
Writeln('}');
end;
procedure EnumerateSubsets(Size: Integer);
var
Bitset: Cardinal;
begin
for Bitset := 0 to (1 shl Size)-1 do begin
PrintBitset(Bitset, Size);
end;
end;
begin
EnumerateSubsets(4);
end.
Sortie
{}
{1}
{2}
{1,2}
{3}
{1,3}
{2,3}
{1,2,3}
{4}
{1,4}
{2,4}
{1,2,4}
{3,4}
{1,3,4}
{2,3,4}
{1,2,3,4}
Et voici une variante seulement énumère les sous-ensembles d'un cardinalité spécifié:
function SetBitCount(Bitset: Cardinal; Size: Integer): Integer;
var
i: Integer;
Mask: Cardinal;
begin
Result := 0;
for i := 1 to Size do begin
Mask := 1 shl (i-1);
if Bitset and Mask<>0 then begin
inc(Result);
end;
end;
end;
procedure EnumerateSubsets(Size, NumberOfSetBits: Integer);
var
Bitset: Cardinal;
begin
for Bitset := 0 to (1 shl Size)-1 do begin
if SetBitCount(Bitset, Size)=NumberOfSetBits then begin
PrintBitset(Bitset, Size);
end;
end;
end;
begin
EnumerateSubsets(4, 2);
end.
Sortie
{1,2}
{1,3}
{2,3}
{1,4}
{2,4}
{3,4}
Cela semble être une question qui revient encore et quelques morceaux de code sont piétinant cette adresse le problème. Un algorithme très agréable dans un code a été écrit, mais il n'a pas été strictement propre C et non portable sur UNIX ou Linux ou tout système POSIX, donc je nettoyé et ajouté des messages d'avertissement, l'utilisation et la capacité à fournir une taille de l'ensemble et la taille de l'sub_set sur la ligne de commande. peigne également [] a été passés à un pointeur plus générale à un tableau d'entiers et calloc utilisé à zéro la mémoire nécessaire pour la taille que jeu on peut vouloir.
Ce qui suit est certifiée ISO IEC 9899: 1999 C propre:
/*********************************************************************
* The Open Group Base Specifications Issue 6
* IEEE Std 1003.1, 2004 Edition
*
* An XSI-conforming application should ensure that the feature
* test macro _XOPEN_SOURCE is defined with the value 600 before
* inclusion of any header. This is needed to enable the
* functionality described in The _POSIX_C_SOURCE Feature Test
* Macro and in addition to enable the XSI extension.
*
* Compile with c99 or with gcc and CFLAGS to include options
* -std=iso9899:199409 -pedantic-errors in order to ensure compliance
* with ISO IEC 9899:1999 C spec.
*
* Code cleanup and transition to comb as a pointer to type ( int * )
* array by Dennis Clarke dclarke@blastwave.org 28 Dec 2012
*
*********************************************************************/
#define _XOPEN_SOURCE 600
#include <stdio.h>
#include <stdlib.h>
/* Prints out a combination like {1, 2} */
void printc( int *comb, int k) {
int j;
printf("{ ");
for ( j = 0; j < k; ++j )
printf("%d , ", *( comb + j ) + 1 );
printf( "\b\b}\n" );
} /* printc */
/**********************************************************************
next_comb(int comb[], int k, int n)
Generates the next combination of n elements as k after comb
comb => the previous combination ( use (0, 1, 2, ..., k) for first)
k => the size of the subsets to generate
n => the size of the original set
Returns: 1 if a valid combination was found
0, otherwise
**********************************************************************/
int next_comb( int *comb, int k, int n) {
int i = k - 1;
++*( comb + i );
while ( ( i >= 0 ) && ( *( comb + i ) >= n - k + 1 + i ) ) {
--i;
++*( comb + i );
}
if ( *comb > n - k) /* Combination (n-k, n-k+1, ..., n) reached */
return 0; /* No more combinations can be generated */
/* comb now looks like (..., x, n, n, n, ..., n).
* Turn it into (..., x, x + 1, x + 2, ...) */
for (i = i + 1; i < k; ++i)
*( comb + i ) = *( comb + ( i - 1 ) ) + 1;
return 1;
} /* next_comb */
int main(int argc, char *argv[]) {
int *comb, i, n, k;
n = 9; /* The size of the set; for {1, 2, 3, 4} it's 4 */
k = 6; /* The size of the subsets; for {1, 2}, {1, 3}, .. it's 2 */
if ( argc < 3 ) {
printf ( "\nUSAGE : %s n k\n", argv[0] );
printf ( " : Where n is the set size and k the sub set size.\n" );
printf ( " : Note that k <= n\n" );
return ( EXIT_FAILURE );
}
n = atoi ( argv[1] );
k = atoi ( argv[2] );
if ( k > n ) {
printf ( "\nWARN : k > n is not allowed.\n" );
printf ( "USAGE : %s n k\n", argv[0] );
printf ( " : Where n is the set size and k the sub set size.\n" );
printf ( " : Note that k <= n\n" );
return ( EXIT_FAILURE );
}
comb = ( int * ) calloc( (size_t) k, sizeof(int) );
for ( i = 0; i < k; ++i)
*( comb + i ) = i;
/* Print the first combination */
printc( comb, k );
/* Generate and print all the other combinations */
while ( next_comb( comb, k, n ) )
printc( comb, k );
free ( comb );
return ( EXIT_SUCCESS );
}
On peut compiler ci-dessus sur une machine à base Opteron ainsi:
$ echo $CFLAGS
-m64 -g -malign-double -std=iso9899:199409 -pedantic-errors -mno-mmx
-mno-sse -fexceptions -fpic -fvisibility=default -mtune=opteron
-march=opteron -m128bit-long-double -mpc80 -Wl,-q
$ gcc $CFLAGS -o combinations combinations.c
Un test trivial rapide avec une taille de jeu de 10 et un sous-ensemble de 6 sera donc:
$ ./combinations 10 6 | wc -l
210
Le calcul est correct:
( 10 ! ) / ( ( 10 - 6 )! * ( 6! ) ) = 210 unique combinations.
Maintenant que le peigne de tableau entier est basé sur un système de pointeur nous ne restreint par la mémoire et le temps disponible. Nous avons donc ce qui suit:
$ /usr/bin/time -p ./combinations 20 6 | wc -l
real 0.11
user 0.10
sys 0.00
38760
semble correct:
( 20 ! ) / ( ( 20 - 6 )! * ( 6! ) ) = 38,760 unique combinations
Nous pouvons maintenant repousser les limites un peu ainsi:
$ ./combinations 30 24 | wc -l
593775
Encore une fois le calcul est d'accord avec le résultat:
( 30 ! ) / ( ( 30 - 24 )! * ( 24! ) ) = 593 775 unique combinations
Ne hésitez pas à repousser les limites de votre système:
$ /usr/bin/time -p ./combinations 30 22 | wc -l
real 18.62
user 17.76
sys 0.83
5852925
Je dois encore essayer quoi que ce soit plus grand, mais le look de mathématiques correctes, ainsi que la sortie jusqu'à présent. Ne hésitez pas à me faire savoir si une correction est nécessaire.
Dennis Clarke dclarke@blastwave.org 28 décembre 2012
À moins que vous ne pouvez pas faire des appels de fonction par une exigence, faites ceci:
select_n_from_list(int *selected, int n, int *list, int list_size):
if (n==0) {
// print all numbers from selected by traversing backward
// you can set the head to a special value or make the head location
// a static variable for lookup
}
for (int i=0; i<=list_size-n; i++) {
*selected = list[i];
select_n_from_list(selected+1, n-1, list+i+1, list_size-i-1);
}
}
Vous avez vraiment besoin d'une sorte de récursion parce que vous avez besoin de stockage automatique des résultats intermédiaires. Permettez-moi de savoir s'il y a exigence particulière qui rend cette solution ne fonctionne pas.
En suivant le lien que David a posté et en cliquant autour de moi a conduit à un article où ils le néologisme « Recherche Banker », qui semble correspondre à votre modèle.
L'article fournit une solution d'exemple en langage C ++, en utilisant récursion:
Je créé ici ce script et a très bien:
$(document).ready(function(){
$("#search").on('click', function(){
var value = $("#fieldArray").val().split(",");
var results = new SearchCombinations(value);
var output = "";
for(var $i = 0; $i< results.length;$i++){
results[$i] = results[$i].join(",");
output +="<li>"+results[$i]+"</li>";
}
$("#list").html(output);
});
});
/*Helper Clone*/
var Clone = function (data) {
return JSON.parse(JSON.stringify(data));
}
/*Script of Search All Combinations without repetitions. Ex: [1,2,3]*/
var SearchCombinations = function (statesArray) {
var combinations = new Array(),
newValue = null,
arrayBeforeLevel = new Array(),
$level = 0,
array = new Clone(statesArray),
firstInteration = true,
indexFirstInteration = 0,
sizeValues = array.length,
totalSizeValues = Math.pow(2, array.length) - 1;
array.sort();
combinations = new Clone(array);
arrayBeforeLevel = new Clone(array);
loopLevel: while ($level < arrayBeforeLevel.length) {
for (var $i = 0; $i < array.length; $i++) {
newValue = arrayBeforeLevel[$level] + "," + array[$i];
newValue = newValue.split(",");
newValue.sort();
newValue = newValue.join(",");
if (combinations.indexOf(newValue) == -1 && arrayBeforeLevel[$level].toString().indexOf(array[$i]) == -1) {
if (firstInteration) {
firstInteration = false;
indexFirstInteration = combinations.length
}
sizeValues++;
combinations.push(newValue);
if (sizeValues == totalSizeValues) {
break loopLevel;
}
}
}
$level++;
if ($level == arrayBeforeLevel.length) {
firstInteration = true;
arrayBeforeLevel = new Clone(combinations);
arrayBeforeLevel = arrayBeforeLevel.splice(indexFirstInteration);
indexFirstInteration = 0;
$level = 0;
}
}
for (var $i = 0; $i < combinations.length; $i++) {
combinations[$i] = combinations[$i].toString().split(",");
}
return combinations;
}*{font-family: Arial;font-size:14px;}
small{font-size:11px}<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>
<label for="">
<input type="text" id="fieldArray">
<button id="search">Search</button>
<br><small>Info the elements. Ex: "a,b,c"</small>
</label>
<hr>
<ul id="list"></ul>
