Zadání: ​http://cw.felk.cvut.cz/​courses/​a4m33pal/​task.php?task=isomers2 „Acyclic Isomers“

Zadání je stejné jako u jedné zkouškové úlohy loni, až na to, že N může mít 3 nebo 5 vazeb, ne jen 3 vazby.

Vstupem je chemický vzorec, např. „C2H2N2O2“, výstupem je počet acyklických izomerů splňující tento vzorec. Jde o počet všech navzájem izomorfních grafů (dokonce stromů, protože tam nejsou cykly), kde jsou uzly označeny jako C, N, O nebo H a mají takový stupeň, kolik ten prvek má vazeb (C 4 vazby, H 1, O 2, N 3 nebo 5).

Řešil bych to nějak takhle: https://gist.github.com/messa/68a04aac63e092da0d09

Postup:

1. Generování stromů, které splňují vstup
2. Vytvořit certifikát stromu, pokud není unikátní, přeskočit strom. Toto lze už během generování, tím se významně sníží počet generovaných stromů.
3. Vypsat počet stromů

S kamarádem jsme to diskutovali a navrhoval bych jiné řešení. Není ověřené, ale má myšlenku. V každém stromě můžeme nalézt jeden či dva uzly, které mají největší hloubku. Tím pádem můžeme začít od tohoto „kořene“ a navěšovat na něj podstromy patřičných velikostí. Je to potřeba dobře promyslet, protože na pořadí navěšených podstromů nezáleží. Certifikáty je potřeba porovnávat pouze u těchto podstromů a to bude značně jednodušší a je možno to také dělat při generování. Mělo by to být efektivnější než přímé generování všech možných stromů.