Détermination des combinaisons possible d'un nombre de 30 chiffres composé de 0 et de 1.

[JakiJake]

Bonjour à tous,

Voici mon problème du moment:
J'aimerais déterminer par un programme en Python, toutes les combinaisons possibles et sans doublons, d'un nombre de 30 chiffres composé uniquement de 15 0 et de 15 1.

Exemple: 000000000000000111111111111111 (P.S: je voudrais garder les 0 non significatifs)

J'ai naturellement d'abords tenté une approche utilisant une génération aléatoire de nombre à partir d'une liste de 0 et de 1. Mais comme cela je ne sais pas comment faire pour que le programme ne fasse pas deux fois la même combinaison au hasard et puisse explorer toutes les combinaisons.

Alors j'ai fait ce algorithme qui détermine réellement toutes les combinaisons possible d'un nombre. Mais il y a des doublons et la quantité de mémoire pour un chiffre de 30 chiffres et juste impossible à gérer. (cf. algo suivant)

A0='000000000000000111111111111111'
def perms(nums):
	if len(nums)==1:
		return [nums]
       	else:
     		all = []
        	for line in perms(nums[:-1]):
        		for i in range(len(nums)):
        	        	all += [line[:i] + nums[-1:] + line[i:]]
        	return all

Alors j'avais pensé à une autre approche: comme le nombre de 30 chiffres et seulement composé de 0 et de 1 j'avais pensé que peut être par un certain moyen il serait possible de scinder le nombre en parties, déterminer toutes les combinaisons possibles de ces parties (car demande moins de mémoire), puis concaténer les possibilités. Mais je ne sais pas vraiment comment faire ça.

Quelqu'un aurait-il une solution à ce problème? ou une piste?

Merci.
-----

[minushabens]

il y a 155117520 chaînes de 30 caractères dont 15 0 et 15 1. Si tu veux les imprimer ça va prendre du temps.

[JakiJake]

Oui merci je sais aussi faire le calcule factorielle seul....

Je sais que ça prend du temps c'est pour ça que je me demande si il y aurait une solution détournée pour obtenir les combinaisons rapidement.

[minushabens]

Il suffit de les engendrer dans l'ordre lexicographique. Tu peux faire ça par exemple avec 30 boucles emboîtées. Mais que vas-tu faire avec tes 155 millions de nombres?

[A voir en vidéo sur Futura]

[minushabens]

===========================

[JakiJake]

merci de ta réponse.
Tu pourrais me donner un exemple des boucles que tu dis?
Si c'est comme je pense ça marchera pas car par exemple la combinaison 101010101010101010101010101010 tu l'obtiendra pas.

Merci .

[Jack]

Si c'est comme je pense

??? Bin ou voudrait bien savoir

ça marchera pas car par exemple la combinaison 101010101010101010101010101010 tu l'obtiendra pas.

Les 30 boucles imbriquées vous générer toutes les combinaisons possibles, dont celle que tu cites. Je ne vois donc pas pourquoi ça ne marcherait pas.

[Bluedeep]

il y a 155117520 chaînes de 30 caractères dont 15 0 et 15 1. Si tu veux les imprimer ça va prendre du temps.

Ca rappelle "Les Neuf Milliards de noms de Dieu" de Arthur C. Clarke

[Bluedeep]

Il suffit de les engendrer dans l'ordre lexicographique. Tu peux faire ça par exemple avec 30 boucles emboîtées. Mais que vas-tu faire avec tes 155 millions de nombres?

Complication inutile.

Il suffit de considérer les possibilités comme étant tous les masques de 30 bits possédant exactement 15 bits à 1.
Ca peut s'obtenir aisément en forcebrutant tous les masques de 0x00007FFF à 0x7fff0001 exclu, puis convertir en chaîne d'affichage ceux ayant la condition "15 bits à 1".

[Bluedeep]

Suite de mon message ci dessus.
Python, je ne connais pas, mais ci joint une solution torchée vite fait en C# basée sur l'idée ci-dessus (forcebrutage de toutes les valeurs entre 0x00007FFF et 0x7fff0001 et sélection) :

				
                UInt32 mask30bits = 0x7FFF;		
		public void DoTruczarbi()
		{
			while (mask30bits < 0x7fff0001)
			{
				if (validate15Bit1and15Bit0(mask30bits))
				{
					string vWo0 = Convert.ToString(mask30bits, 2); // adjonction des leading 0
					string display = new string('0', 30 - vWo0.Length) + vWo0;
					Console.WriteLine(display);
				}
				mask30bits++;
			}
		}

		/// <summary>
		/// On compte les bits à 1 sur 30 bits.
		/// </summary>
		/// <param name="v"></param>
		/// <returns></returns>
		private bool validate15Bit1and15Bit0(UInt32 v)
		{
			UInt32 totalCount1 = 0;
			for(byte i = 0; i < 30; i++)
			{
				totalCount1 += (v >> i) & 0x01; ;
				if (totalCount1 > 15)
					return false;
			}
			return (totalCount1 == 15);
		}

[minushabens]

mais c'est qu'il y a beaucoup plus de chaînes de 0 et de 1 de longueur 30 que de chaînes vérifiant la condition.

[Jack]

mais c'est qu'il y a beaucoup plus de chaînes de 0 et de 1 de longueur 30 que de chaînes vérifiant la condition.

D'où la fonction validate15Bit1and15Bit0 qui les filtre.

[minushabens]

Ok finalement on garde une chaîne sur 7, ce n'est pas si mal, même si ce n'est pas élégant. On peut engendrer les bonnes chaînes et seulement elles avec des matrices d'Hadamard (qui sont constituées de 1 et de -1, il faut enlever 1 à tout le monde à la fin).

[Bluedeep]

Ok finalement on garde une chaîne sur 7, ce n'est pas si mal, même si ce n'est pas élégant. On peut engendrer les bonnes chaînes et seulement elles avec des matrices d'Hadamard (qui sont constituées de 1 et de -1, il faut enlever 1 à tout le monde à la fin).

Oui, mais reste à démonter que la solution "élégante" est plus performante; sur ce genre de cas, c'est justement pas toujours évident.

[minushabens]

ce n'est certainement pas plus performant, puisqu'il faut faire des produits de matrices, et puis le résultat serait une énorme matrice à 30 colonnes et 155 millions de lignes. Remarque que ton programme il va cracher 155 millions de lignes dans un fichier... de toutes façons JakiJaje n'a pas dit ce q'il voulait faire avec ces chaînes (ou nombres)

[Bluedeep]

ce n'est certainement pas plus performant, puisqu'il faut faire des produits de matrices, et puis le résultat serait une énorme matrice à 30 colonnes et 155 millions de lignes. Remarque que ton programme il va cracher 155 millions de lignes dans un fichier... de toutes façons JakiJaje n'a pas dit ce q'il voulait faire avec ces chaînes (ou nombres)

Pour rire, j'ai lancé l'exécution (avec une petite variante : je stock dans une liste en mémoire); ce qui curieux c'est que je trouve 310235024 valeurs (après 124 secondes de calcul .....), soit le double.
Lequel des deux a tort ? (la structure même de mon exemple l'empêche a priori de travailler deux fois la même valeur puisque je procède par incrément).

[minushabens]

Je vois ça comme ça: déterminer une chaîne de 15 0 et 15 1 c'est équivalent à donner les places des 1. Donc il y a autant de chaînes que de façons de choisir 15 places parmi 30, ou 15 éléments dans un ensemble de 30 éléments, c'est le coefficient binomial C(30,15) = 30!/(15!*15!) = (30*29*...*16)/(15*14*...*2)

[Stan_94]

Bonjour,
si j'ai bien suivi, on a effectivement le nombre de combinaison de p élements (ici mettre 15 symboles "1") parmis n (30 cases "0") donne bien 155117520


Et moi aussi, curieux comme je suis, j'aimerai bien savoir à quoi ça va servir...

[jiherve]

Bonjour,
Une piste possible de simplification : toute valeur correcte en génère 29 autres(mais pas forcement toute différentes) par décalage circulaire;
JR

[minushabens]

Je ne sais pas ce qui cloche dans le programme de Bluedeep...

voici une méthode récursive:

je généralise un peu le problème : il s'agit d'énumérer tous les sous-ensembles de {1,...,n} ayant exactement k éléments (dans le problème posé n=30 et k=15). La fonction chechée est notée f(k,n)

- si k==1 ou si k==n la solution est triviale

- sinon, on distingue 2 cas, selon que n est dans le sous-ensemble ou pas, et on appelle f(k-1,n-1) <il faudra ajouter n aux sous-ensembles> puis f(k,n-1)

Ca oblige à gérer tous les sous-ensembles en mémoire simultanément sous forme de liste, on ne peut pas les cracher les uns après les autres comme dans le méthode de Bluedeep, donc à mon avis ça va coincer un peu avec 15 et 30.