Combinaisons !

[pascal16]

pff, moi non plus, toujours pas de technique de dénombrement
pour le 9/3 de Lostounet
123
145
167
189
246
278
347
489
est différent et a aussi 8 solutions

[Ben314]

A VERIFIER :

Code: Tout sélectionner

import random

def Cnk(n,k):
  T=[]
  if k<0 or k>n: return T
  TB=range(1,k+1); T.append(TB[:])
  if k==0 or k==n: return T
  i=k-1
  while i>=0:
    p=TB[i]+1
    while i<k:
      TB[i]=p; i=i+1; p=p+1
    T.append(TB[:])
    i=k-1
    while i>=0 and TB[i]==i+n-k+1:
      i=i-1
  return T

def NbCommun(T1,T2):
  nb=0; i=0; j=0;
  while i<len(T1) and j<len(T2):
    if T1[i]<T2[j]:
      i=i+1
    elif T1[i]>T2[j]:
      j=j+1
    else:
      i=i+1; j=j+1; nb=nb+1
  return nb


def Soluce(n,k):
  T1=[]; T2=Cnk(n,k);
  while len(T2)>0:
    i=int(len(T2)*random.random())
    TB=T2[i]; del T2[i]
    i=0
    while i<len(T1) and NbCommun(T1[i],TB)<=1:
      i=i+1
    if i==len(T1):
      T1.append(TB)
  return T1

def Test(n,k):
  max=0
  for i in range(1000):
    T=Soluce(n,k)
    if len(T)>max:
      max=len(T)
      print len(T),T
  return max

Test(9,3)

8 [[1, 3, 6], [3, 4, 7], [2, 5, 9], [1, 8, 9], [6, 7, 8], [2, 3, 8], [1, 2, 7], [4, 5, 6]]
9 [[3, 4, 5], [1, 7, 9], [2, 5, 8], [1, 3, 8], [4, 8, 9], [6, 7, 8], [2, 6, 9], [1, 4, 6], [2, 3, 7]]
10 [[3, 4, 8], [2, 3, 7], [2, 6, 8], [2, 4, 5], [1, 3, 5], [1, 8, 9], [4, 7, 9], [5, 7, 8], [1, 6, 7], [5, 6, 9]]
12 [[3, 7, 9], [1, 7, 8], [3, 4, 8], [2, 5, 8], [2, 4, 9], [1, 5, 9], [3, 5, 6], [4, 5, 7], [1, 4, 6], [2, 6, 7], [6, 8, 9], [1, 2, 3]]
Donc pour N=9 et K=3, il semblerais qu'il y ait des solutions avec 12 sous ensembles à 3 éléments (et vu les 1000 tests on peut vraisemblablement conjecturer qu'il n'y a pas mieux)

[Lostounet]

Assez perturbant.. je vois pas comment j'aurais pu mieux faire dans mon énumération. Peut-être que j'ai trop abusé du '1' ce qui m'a fait trop de contraintes...

[lapuce798]

Bonjour à tous,
Est-ce qu'il est nécessaire de remplir des cellules sur Excel afin d'utiliser le programme qu'a conçu Ben?

[Ben314]

C'est du Python : tu peut charger n'importe où un interpréteur python (gratuit), voire un environnement python, style Spyder et/ou trouver un interpréteur en ligne.

Mais si tu veut faire des test avec des valeurs plus grandes, il faudrait nettement optimiser l'algo : j'y connait pas grand chose en python donc je sais pas comment sont gérés "en vrai" les "listes" sous python, mais d'utiliser comme je le fait des instruction du style "enlever un élément au milieu d'une liste", ça m'étonnerais que ce soit bien malin au niveau complexité de l'algo.

[lapuce798]

Je vais faire cela alors. En tout cas, merci à tous pour le temps passé. Vous m'avez fait bien avancé !
Bonne soirée

[lapuce798]

Après avoir télécharger Python, la formule ne fonctionne pas "invalid synthax" alors que j'ai pris la formule telle quelle pour essayer d'obtenir les 12 sous ensemble.
Je crois comprendre que le problème vient de " print len(T),T "
Une idée ?

[zygomatique]

salut

si je comprends bien :

un fois choisi un sous-ensemble E = {a, b, c, d, e} de I = [[1, 48]] je ne peux que considérer les sous-ensembles F de I qui n'ont pas plus de un élément en commun avec E

et ainsi de suite ...

en choisissant E1 = {1, 2, 3, 4, 5}

alors pour E2 il y a deux cas :

soit il a un élément en commun avec E1 (on peut décider que ce soit 5 (le max)
soit il n'a aucun point commun avec E1

E2 = {5, 6, 7, 8, 9} ou E2 = {6, 7, 8, 9, 10}

pour E3 il y a quatre cas (enfin suivant qui est E2) :

soit il n'a aucun point commun avec E1 U E2
soit il a un point en commun avec E1 (qui n'est pas 5)
soit il a un point en commun avec E2 (qui n'est pas 5)
soit il a un point commun avec E1 et E2 donc 5

... ouais sacré galère ...


EDIT : ça papote dur ... j'en étais à la première page au moment de taper mon laïus ...

[Ben314]

Après avoir télécharger Python, la formule ne fonctionne pas "invalid synthax" alors que j'ai pris la formule telle quelle pour essayer d'obtenir les 12 sous ensemble.
Je crois comprendre que le problème vient de " print len(T),T "
Une idée ?

Oui, c'est que j'ai tapé ça à la "vite fait" sous l'environnement que j'ai au boulot et que c'est l'ancienne version de python 2.7. Avec la version 3.4, ça donne ça :

Code: Tout sélectionner

import random

def Cnk(n,k):
  T=[]
  if k<0 or k>n: return T
  TB=list(range(1,k+1)); T.append(TB[:])
  if k==0 or k==n: return T
  i=k-1
  while i>=0:
    p=TB[i]+1
    while i<k:
      TB[i]=p; i=i+1; p=p+1
    T.append(TB[:])
    i=k-1
    while i>=0 and TB[i]==i+n-k+1:
      i=i-1
  return T

def NbCommun(T1,T2):
  nb=0; i=0; j=0;
  while i<len(T1) and j<len(T2):
    if T1[i]<T2[j]:
      i=i+1
    elif T1[i]>T2[j]:
      j=j+1
    else:
      i=i+1; j=j+1; nb=nb+1
  return nb


def Soluce(n,k):
  T1=[]; T2=Cnk(n,k);
  while len(T2)>0:
    i=int(len(T2)*random.random())
    TB=T2[i]; del T2[i]
    i=0
    while i<len(T1) and NbCommun(T1[i],TB)<=1:
      i=i+1
    if i==len(T1):
      T1.append(TB)
  return T1

def Test(n,k):
  Max=0
  for i in range(100):
    T=Soluce(n,k)
    if len(T)>Max:
      Max=len(T)
      print (len(T),T)
  return Max
 
Test(9,3)


(il m'a fallu des plombes pour trouver le list(range(...)))
Qui marche par exemple là :
https://www.tutorialspoint.com/execute_ ... online.php

[lapuce798]

Merci pour tout. J'ai réussi à lancer la formule par moi-même. Quand j'ai vu la formule et essayer de la décrypter, j'ai compris le temps passé. Bonne soirée