Come ottenere tutte le operazioni associative algebriche su un insieme finito mediante un algoritmo efficiente?

Il numero di operazioni binarie su un set di 2 elementi è 2^(2*2)=16. enter image description here
Numero di un'operazione binaria associativa sul set solo 8.

Numero di un'operazione binaria su un insieme di 3 elementi è 3^(3 * 3) = 19683.
Il numero di operazioni binarie associative su quel set è solo 113. Come sapere quante operazioni binarie associative ci sono su un insieme di n elementi?Come ottenere tutte le operazioni associative algebriche su un insieme finito mediante un algoritmo efficiente?

Anche per ottenere tutte queste 113 operazioni e scrivere in un file, è necessario scrivere un programma.
se tenterò di ottenere tutte le operazioni del 19683 e quindi controllerò la proprietà associativa "a * (b c) == (a b) * c" per tutte le operazioni del 19683, funzionerà ma questo dovrebbe richiedere un molto tempo per n = 4 elementi!
Come scrivere un algoritmo efficiente per risolvere questo compito?
Per favore aiutatemi!

fonte

2014-07-09 IremadzeArchil19910311

La tua domanda è modo per larga, e probabilmente anche non molto ben messo a fuoco per SO. SO parla di programmazione e non di Combinatorics. –

@JensGustedt Questo problema riguarda più gli algoritmi rispetto alla combinatoria. Certo, hai bisogno della combinatoria per analizzare l'algoritmo (un'implementazione ingenua sarebbe qualcosa come 'O (n^(n^2))' in complessità), ma non si tratta di combinatoria. Sono d'accordo che questo post potrebbe essere più adatto [programmers SE] (http://programmers.stackexchange.com), dal momento che menzionano algoritmi specificatamente in [le loro FAQ] (http://programmers.stackexchange.com/tour). – bheklilr

@bheklilr: Beh, SO ha almeno un [tag algoritmo] (http://stackoverflow.com/tags/algorithm/info) (e un tag per l'algebra astratta e anche uno per i semigruppi). Ma penso, è troppo ampio, una buona risposta probabilmente sarebbe molto lunga. Infine, non c'è nulla che OP abbia provato fino ad ora (è una domanda "gimme teh algo"). IremadzeArchil: Forse http://math.stackexchange.com/? In realtà, stai chiedendo "quanti semigruppi con n elementi esistono?" – mafso

Più che inventare il proprio algoritmo, questo è un compito per un modello matematico di ricerca. Per questo compito, mi consiglia in particolare mace4, quale parte di the LADR library. È specificamente sintonizzato su problemi algebrici come questo. L'ingresso (Diamo il nome semigroups.in) sarebbe simile:

formulas(sos). 
    (x * y) * z = x * (y * z). 
end_of_list.

E poi eseguirlo dal mace4 -n 4 -N 4 -m 10000 <semigroup.in (per tutti i modelli a 4 elementi e stampare fino a 10000 di loro) produce una lunga uscita come

... 

============================== MODEL ================================= 

interpretation(4, [number=2331, seconds=0], [ 

     function(*(_,_), [ 
          1, 2, 3, 3, 
          2, 3, 3, 3, 
          3, 3, 3, 3, 
          3, 3, 3, 3 ]) 
]). 

============================== end of model ========================== 

============================== STATISTICS ============================ 

For domain size 4. 

Current CPU time: 0.00 seconds (total CPU time: 0.11 seconds). 
Ground clauses: seen=64, kept=64. 
Selections=2132, assignments=8520, propagations=6194, current_models=2331. 
Rewrite_terms=210696, rewrite_bools=65151, indexes=11452. 
Rules_from_neg_clauses=586, cross_offs=3767. 

============================== end of statistics ===================== 

User_CPU=0.11, System_CPU=0.26, Wall_clock=0. 

Exiting with 2331 models.

Come potete vedere, è molto veloce.

La biblioteca contiene molti altri strumenti, come ad esempio isofilter che permette di filtrare le varianti isomorfe di un'algebra ecc

fonte

2014-07-09 20:35:11

'Wall_clock = 0' A quanto pare, vantarsi è una funzione supportata nativamente da questa libreria. Hanno davvero pensato a tutto ... –

@ParthianShot Sembra più una funzionalità non implementata. –

Come ottenere tutte le operazioni associative algebriche su un insieme finito mediante un algoritmo efficiente?

risposta

Problemi correlati