Parties d'un ensemble, scilab

Clairon · February 2019

Aux pros de Scilab.

Avez-vous une idée pour faire afficher toutes les parties de {1,..,n} ?
Une petite fonction récursive ferait l'affaire, mais ...

Je ne vois pas comment stocker les parties de {1,2} en Scilab, sans qu'il ne "mélange tout".
J'ai pensé à ], [1], [2], [1,2, mais le résultat n'est pas du tout satisfaisant pour pouvoir construire la fonction récursive.

nicolas.patrois · February 2019

Pourquoi ne pas utiliser une sélection en utilisant des bits ?
Si ton ensemble contient $n$ éléments, tu as $2^n$ parties donc tu écris en binaire tous les nombres entre $0$ et $2^{n-1}$ et tu crées tes parties en sélectionnant les éléments où le 1 apparaît.
En Python :

def sousensemble(it):
  tup=tuple(it)
  n=len(tup)
  for i in range(2**n):
    s=bin(i)[2:]
    s="0"*(n-len(s))+s
    print([tup[j] for j in range(n) if s[j]=="1"])

Clairon · February 2019

Bonne idée, merci Nicolas.
Je tente cela en fin d'après-midi !

Rescassol · February 2019

Bonsoir,

Ou encore:

import itertools as it

n=4
tab=[p for k in range(n+1) for p in it.combinations(range(1,n+1),k)]
print(tab)

Tu peux d'abord tester:

tab=[p for p in it.combinations([1,2,3,4],2)]
print(tab)

Cordialement,

Rescassol

Clairon · February 2019

Salut Rescassol,

Ne pas oublier que je suis "sous Scilab" (programme officiel, oblige !).

nicolas.patrois · February 2019

C’est pour ça que je n’ai pas proposé itertools.

Rescassol · February 2019

Bonsoir,

Comme Nicolas, je t'ai donné du Python, tu n'y as pas droit ?

Cordialement,

Rescassol

Rescassol · February 2019

Bonsoir,

Ce code, donné par Gilles dans un fil voisin, est peut être plus facilement traduisible:

def combin(L,k):
    if k==0:
        return [[]]
    if k>len(L):
        return []
    return combin(L[1:],k)+[[L[0]]+M for M in combin(L[1:],k-1)]

Cordialement,

Rescassol

Clairon · February 2019

Hello Rescassol et Nicolas.

Voilà ce que ça donne. Merci Nicolas.

-->k = 19 ;

-->m = dec2bin(k) 
 m  =
 
 10011   

-->typeof(m) 
 ans  =
 
 string   


-->function I = MotBinaireToPartie(m)
-->    I = []
-->    for i = 1:length(m)
-->        if part(m, i)=='1' then
-->          I = [I,i]
-->        end
-->    end    
-->endfunction


-->MotBinaireToPartie(m)
 ans  =
 
    1.    4.    5.

Coder avec Scilab, c'est vraiment "prise de tête". Mais j'y suis arrivée !

nicolas.patrois · February 2019

Gaffe à bien avoir des décompositions binaires de la même longueur.

Clairon · February 2019

Hum, tu as raison, Nicolas.
Bon, j'arrête, ça m'agace.
Scilab, c'est nul !
(je sais, ce n'est pas fait pour faire ce que je veux, mais quand même !)

Clairon · February 2019

C'est pas du tout encore opérationnel. Car pour l'instant, il n'y a que l'affichage.
Je ne vois pas comment stocker l'information...
Une liste des listes n'a pas l'air d'exister en Scilab.

-->function I = MotBinaireToPartie(m)
-->    I = []
-->    n = length(m)
-->    for i = 1:n
-->        if part(m, n-i+1)=='1' then
-->          I = [I,i]
-->        end
-->    end    
-->endfunction

-->function E = Parties(n)
-->    E = []
-->    for k = 0:(2^n-1)
-->        m = dec2bin(k) 
-->        E = MotBinaireToPartie(m)
-->        disp(E)
-->        // E = [E, MotBinaireToPartie(m)]
-->    end
-->endfunction

-->disp(Parties(4))
 
     []
 
    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.  
 
    1.    2.    3.    4.

Clairon · February 2019

-->function I = MotBinaireToPartie(m)
-->    I = []
-->    n = length(m)
-->    for i = 1:n
-->        if part(m, n-i+1)=='1' then
-->          I = [I,i]
-->        end
-->    end    
-->endfunction


-->function E = Parties(n)
-->    E = list()
-->    for k = 0:(2^n-1)
-->        m = dec2bin(k) 
-->        E = lstcat(E, list(MotBinaireToPartie(m)))
-->    end
-->endfunction


-->P = Parties(4)
 P  =
 
 
       P(1)
 
     []
 
       P(2)
 
    1.  
 
       P(3)
 
    2.  
 
       P(4)
 
    1.    2.  
 
       P(5)
 
    3.  
 
       P(6)
 
    1.    3.  
 
       P(7)
 
    2.    3.  
 
       P(8)
 
    1.    2.    3.  
 
       P(9)
 
    4.  
 
       P(10)
 
    1.    4.  
 
       P(11)
 
    2.    4.  
 
       P(12)
 
    1.    2.    4.  
 
       P(13)
 
    3.    4.  
 
       P(14)
 
    1.    3.    4.  
 
       P(15)
 
    2.    3.    4.  
 
       P(16)
 
    1.    2.    3.    4.

Math Coss · February 2019

À la limite, à quoi est-ce que ça sert de les stocker ? Tu peux calculer la partie qui correspond à un entier lorsque tu en as besoin.

Parties d'un ensemble, scilab

Réponses

Lettre d'information