[PYTHON] Tutte le combinazioni possibili di un'insieme

Linguaggi di programmazione: php, perl, python, C, bash e tutti gli altri.
Avatar utente
marco2
Prode Principiante
Messaggi: 146
Iscrizione: sabato 28 aprile 2012, 13:49
Desktop: Unity
Distribuzione: Ubuntu 14.04
Località: Bolzano

[PYTHON] Tutte le combinazioni possibili di un'insieme

Messaggio da marco2 »

Buonasera a tutti,

apro questo thread per una richiesta al quanto insolita: devo scrivere un programma in python che dato un'insieme di x elementi, calcoli quanti sottoinsiemi nati dalla combinazione di un numero y di elementi (che varia da 1 al numero di elementi) si possono creare. Fino a qua non ho avuto problemi. Lo scoglio reale è che python non tiene conto che {1,2,3} e {3,2,1} sono lo stesso insieme, aggiungendo quindi, un sacco di insiemi che invece io non devo considerare. Sapete aiutarmi? Qua sotto posto il codice che ho già scritto. Grazie in anticipo!
Marco

Codice: Seleziona tutto

#!/usr/bin/python
# -*- coding: utf8 -*-
# Copyright (c) 2015, marco2
from sys import stdout
from itertools import product
print "#"*70
print "InsiemCounter"
print "Realizzato per dimostrare scientificamente teorie matematiche"
print "#"*70
print ""
stdout.write("Inizzializzo la lista...")
l = []
print " [OK]"
def create(n):
    a = 0
    l = []
    t = "Genero un insieme l di %s elementi..." %(n)
    stdout.write(t)
    while a <= n-1:
        s = "%s" %(a)
        l += [s]
        a += 1
    if len(l) != n:
        print " [ERROR]"
        print "Log: "
        print "Richiesti %s elementi" %(n)
        print "Generati %s elementi" %(len(l))
        l
    else:
        print " [OK]\nGenerato un insieme di %s elementi" %(len(l))
        return l

print "Non superare il 9 o potrebbero ricorrere degli errori"
l = create(input("Numero di elementi da inserire: "))
n = len(l)-1
ins = [l,[]]
while n != 0:
    combo_pack = product(l, repeat = n)
    for combo in combo_pack:
        c = 0
        a = "".join(combo)
        now = []
        while c != len(a):
            if a[c] not in now:
                now += a[c]
            c += 1
        c = 0
        d = len(ins)
        ins += [now]
    n = n-1
Marco2
1001001
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1506
Iscrizione: mercoledì 22 dicembre 2010, 18:09
Desktop: Unity
Distribuzione: Ubuntu 14.04.1 LTS 64bit
Località: Verona

Re: [PYTHON] Tutte le combinazioni possibili di un'insieme

Messaggio da 1001001 »

Se devi solo contare il numero di possibili sottoinsiemi di cardinalità y non serve generarli tutti, basta usare il coefficiente binomiale (https://it.wikipedia.org/wiki/Coefficiente_binomiale)
"I find your lack of faith disturbing."
Avatar utente
crap0101
Rampante Reduce
Rampante Reduce
Messaggi: 8242
Iscrizione: martedì 30 ottobre 2007, 6:33
Desktop: LXDE
Distribuzione: Ubuntu 18.04.1 LTS
Sesso: Maschile
Località: TO
Contatti:

Re: [PYTHON] Tutte le combinazioni possibili di un'insieme

Messaggio da crap0101 »

più che python che non niente conto sei tu a dover usare gli strumenti giusti.
Se ti interessa _elencare_ tutte le combinazioni nel modulo iterools da cui importi product() ci sono altri generatori che fanno esattamente quello; se però vuoi fare tutto da te allora dovresti anche usare i contenitori "giusti", o almeno quelli che ti semplificano i controlli (tipo set()), o ancora meglio rivedere e semplificare il codice, perchè effettivamente non fa quello che vorresti. btw, nella doc di itertool ci sono implementazioni d'esempio per tutte le funzioni e generatori del modulo.
http://www.gnu.org/ http://boinc.berkeley.edu/ http://www.python-it.org/
- Ricorda le ultime parole di suo padre: «Sta' alla larga dalle chiese, figlio. La sola cosa per cui hanno la chiave è il merdaio. E giurami che non porterai mai un distintivo della legge» - W.S. Burroughs
Avatar utente
ubuntumate
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1180
Iscrizione: giovedì 28 maggio 2015, 18:18
Distribuzione: Windows 7
Sesso: Maschile
Località: Milano

Re: [PYTHON] Tutte le combinazioni possibili di un'insieme

Messaggio da ubuntumate »

Non è particolarmente difficile,si tratta di applicare le basi del calcolo combinatorio.Se abbiamo N elementi allora il numero di possibile di combinazioni possibili in classe K è dato da fattoriale(N) -fattoriale(N-K).Senza ripetizioni basta dividere per K.
EDIT:correggo la formula perché è sbagliata.È N!/(N - K)!K!.Per esempio vogliamo sapere quante coppie di assi possiamo formare in un mazzo di carte francesi.Abbiamo 4 assi e vogliamo fare delle coppie.Faremo 4 x 3 = 12 / 2 = 6 .
Software engineers shall participate in lifelong learning regarding the practice of their profession and shall promote an ethical approach to the practice of the profession.
ACM/IEEE Code of ethics.
Avatar utente
marco2
Prode Principiante
Messaggi: 146
Iscrizione: sabato 28 aprile 2012, 13:49
Desktop: Unity
Distribuzione: Ubuntu 14.04
Località: Bolzano

Re: [PYTHON] Tutte le combinazioni possibili di un'insieme

Messaggio da marco2 »

Buonasera a tutti,

grazie delle numerose risposte.
Il programma serve appunto per dimostrare il Coefficiente binomiale.
crap0101, ti dispiacerebbe farmi un esempio di codice, giusto per farmi un'idea di ciò che intendi?

Grazie mille.
Marco
Marco2
Avatar utente
M_A_W_ 1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 856
Iscrizione: venerdì 15 febbraio 2013, 3:57
Desktop: KDE
Distribuzione: SuSE
Sesso: Maschile
Località: Un luogo geometrico
Contatti:

Re: [PYTHON] Tutte le combinazioni possibili di un'insieme

Messaggio da M_A_W_ 1968 »

Non è particolarmente chiaro in che modo tu intenda "dimostrare il coefficiente binomiale" e come ciò si possa relazionare con la generazione di un numero finito di sottoinsiemi.
Vuoi dimostrare automaticamente per induzione la formuletta di conteggio degli oggetti combinatori elementari denominati combinazioni semplici?
Vuoi tentare una dimostrazione combinatoria assistita da software?
Vuoi derivare logicamente tale formuletta dai lemmi fondamentali di conteggio (es. regola del prodotto e della somma di Liu, regola del quoziente, piccionaia, falling powers...) tramite il teorema di Herbrand e un po' di algebra simbolica rule-based (es. Peano o Robinson)?
Oppure quanto ho scritto finora ti suona incomprensibile e hai in mente un significato non standard o scolastico di dimostrazione? Vuoi semplicemente mostrare (non "dimostrare") qualche esempio pratico di uso del CB per piccoli valori?

Le domande che sorgono dinanzi a simili dichiarazioni di intenti sono sempre molte. Specialmente dopo tanti lustri di esperienza telematica e di teoria della dimostrazione automatica.
Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo...

"...in una società che sembra sempre più spaventata dai problemi troppo articolati e che rigetta come un corpo estraneo ogni elemento di complessità, sapremo ancora come utilizzare il parere degli esperti?"
Scrivi risposta

Ritorna a “Programmazione”

Chi c’è in linea

Visualizzano questa sezione: 0 utenti iscritti e 9 ospiti