Arrange items in a set based on a set of rules

Is there any special design pattern or algorithm available for this problem?

There are multiple items (A1,A2,A3 ..An) and I want to arrange them, some of them are related to the other ones and only can comes before or after them.

For example A2 can be placed only after A4 and “An” can be placed at the end of the set. But the point is that the sequence of some items can be interchangeable and based on sequence some items should not be in the set.

For examlpe consider this scenario

There are 6 items

A1, A2, A3, A4, A5, A6

And the rules are

A1 must be at the first place (always),

A2 can be after A4,

A5 can be in the set only if A3 has been there before it

A6 comes at the end of the set and it is a mandatory member but it only can be there if all other valid items have been in the set before it !

Valid sets are like this

A1, A4, A3, A2, A5, A6

A1, A4, A2, A6

Invalid sets

A4, A3, A2, A5, A6 (A1 is missed)

A1, A4, A3, A2, A5 (A6 is missed)

A1, A3, A2, A6 (A2 only comes after A4)

Note: I have to validate the input! and input can have any order! I mean I don’t want to sort the items I want to validate an input set from the user

As a sample, based on my example above the below sets are all valid

{A1, A4, A3, A2, A5, A6}

{A1, A4, A2, A3, A5, A6}

{A1, A3, A4, A2, A5, A6}

{A1, A3, A5, A4, A2, A6} 开发者_JS百科

So user might enter any of these as an input and all of them are valid based on the defined conditions!

Any idea of any special design pattern or algorithm which can be applied to this problem? Number of items or the rules might get change in the future!

“BalusC” had been removed my “Design pattern” tag! But so far I think the best way to handle this problem might be the command pattern. I mean I considered each item as a command from the user and I defined a validation process for the command (“canExecute”) I am going to code it in C# and since ICommand interface in .Net has “canExecute” method I think I will use it to validate the command based on condition. (Execute method just added the item to the result set!) I have not coded it yet so I am not sure how complicated the validation process might be. I thought maybe someone has some idea how I can combine the command pattern and a validation algorithm to achieve the goals.

I might be wrong so any idea or suggestion can be helpful. Thanks.

This should be solvable with a variation of a topological sort.

Basically, you build a directed acyclic graph where there is an edge from A_i to A_j if A_i must come before A_j in the result. The topological sort will then give you a valid order for the A's.

This will not deal with the rule that some items may be missing, but that should be simple to layer on top of this.

A1, A4, A2, A6

cannot be a valid set, because

A6 comes at the end of the set and it is a mandatory member but it only can be there if all other valid items have been in the set before it