0
$\begingroup$

Summary: I have a tree, containing car parts, from which I need to build all valid combinations of these parts.

Parts can be required - every build must contain them.

Parts can be optional.

Parts can conflict with other parts.

Parts can have optional parts inside them.

Example tree:

Car
| - Motor (required)
| - - V8
| - - V12
| - - - Colour (optional)
| - - - - Black
| - - - - Chrome
| - Transmission (required)
| - - Mechanical
| - - Automatic
| - Wheels (optional)
| - - Basic
| - - Fancy
| - - - Colour (optional)
| - - - - Red
| - - - - Blue
| - BodyStyle (optional)
| - - Hatchback (conflicts with Motor.V12)
| - - Buggy (conflicts with Motor.V8)

Valid builds for this tree:

Car | Motor.V8 | Transmission.Automatic
Car | Motor.V8 | Transmission.Automatic | Wheels.Basic
Car | Motor.V12.Colour.Black | Transmission.Automatic | Wheels.Basic
Car | Motor.V8 | Transmission.Automatic | BodyStyle.Hatchback
Car | Motor.V12 | Transmission.Mechanical | Wheels.Fancy | BodyStyle.Buggy
Car | Motor.V12 | Transmission.Mechanical | Wheels.Fancy.Colour.Red | BodyStyle.Buggy

What algorithm should I look for, that can solve this task

$\endgroup$
  • $\begingroup$ Can you edit your question to ask a more specific question? I don't understand what you are asking. $\endgroup$ – D.W. Sep 16 at 2:01
  • $\begingroup$ @D.W. I am looking for a suitable algorithm, that can generate me all permutations or nodes of a tree, filtering results by provided rules $\endgroup$ – Neonailol Sep 16 at 5:29
  • $\begingroup$ Use exhaustive search. $\endgroup$ – Yuval Filmus Sep 16 at 7:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.