Come posso ottenere tutte le partizioni di un elenco in Mathematica?

Per partizione di una lista, intendo un insieme di sottoinsiemi di elementi della lista in modo tale che l'intersezione di qualsiasi coppia distinta di sottoinsiemi sia vuota e l'unione di tutti i sottoinsiemi sia uguale alla lista originale.Come posso ottenere tutte le partizioni di un elenco in Mathematica?

Per esempio, se la mia lista di ingresso è {1,π,x} Poi vorrei una funzione che restituisce

{ {{1},{π},{x}}, {{1,π},{x}}, {{1,x},{π}}, {{1},{x,π}}, {{1,π,x}} }

fonte

2011-11-29 Michael

@yoda: L'OP potrebbe essere confusa con la terminologia. Queste non sono partizioni, sono d'accordo. – Blender

@Blender Sì, mi sono appena reso conto che avrebbe potuto ottenere qualcos'altro. – abcd

@Blender, yoda: Queste sono [partizioni nel senso degli insiemi] (http://en.wikipedia.org/wiki/Partition_of_a_set), non solo nel senso del comando Mathematica [Partizione] (http: // reference .wolfram.com/mathematica/ref/Partition.html). – Simon

Uso adattato codice http://mathforum.org/advanced/robertd/bell.html

BellList[1] = {{{1}}}; 
BellList[n_Integer?Positive] := Join @@ 
    (ReplaceList[#, 
    {{b___, {S__}, a___} :> {b, {S, n}, a}, 
    {S__} :> {S, {n}}} 
    ] & /@ BellList[n - 1]) 

s = {a, b, c, d, e}; 

bell = [email protected]@s /. n_Integer :> s[[n]]

Oppure, ovviamente, il pacchetto Combinatorica ha questa funzione (SetPartitions) già!

Needs["Combinatorica`"] 

comb = SetPartitions[{a, b, c, d, e}]

controllo che entrambi restituiscono lo stesso risultato (ma in ordine diverso)

Complement[bell, comb] == {} 
[email protected] == [email protected] 
(* Both of the above return True *)

fonte

2011-11-29 02:12:48

@ Mr.Wizard, mi ci vorrà un po 'di tempo per analizzare mentalmente, ma per quanto ne so, fa il lavoro, grazie! – Michael

@ Michael, ho dimenticato di controllare questa funzione nelle librerie standard. Guarda l'aggiornamento che ho appena fatto. –

@Simon, grazie per la modifica. –

Vorrei iniziare con un Powerset del set (utilizzare Subsets[x]) e poi filtrare quelli in cui Union[x] del set non è il set originale.

Un po 'lento, ma lo trovo intuitivo.

fonte

2011-11-29 01:58:43 Blender

Unione di '{{1, x}, {π}}' non è il set originale; anche se l'OP lo ha chiesto. –

@BillyONeal perché dici che l'unione {1, x} e {π} non è uguale a {1, π, x}? L'ordine degli elementi di un set non ha importanza per la definizione del set ... – Michael

@Blender: I corretti. :) –

Come posso ottenere tutte le partizioni di un elenco in Mathematica?

risposta

Problemi correlati