# Randomly sorting a list where some states are illegal?

I want to make a randomizer for the items in the game La-Mulana. However, some arrangements of items would mean that the game cannot be completed. Sometimes there's only one group of items required to pass an obstacle, other times, there are multiple groups of items which can pass an obstacle.

For example, to reach the Chamber of Birth, you need to have the Feather, Grapple Claw, Hermes' Boots, and Plane Model, or have the Isis Pendant and Hermes' Boots, or kill the fifth boss and have the Plane Model. This means that anything that puts the Hermes' Boots and the Plane Model in the Chamber of Birth makes the game impossible to complete.

Effectively, I'm trying to put a list in random order where some items can never be within a range of indices and some items can only be within a range of indices if others are within a second range of indices. Is there a better way of doing this than to reject and re-generate illegal configurations?

• Do you care about all valid states having the same probability of being generated? – IllusiveBrian Mar 3 '17 at 17:17
• It would be nice, but if that's expensive, then not really. – Smurfton Mar 3 '17 at 18:10
• Can you indicate roughly what percentage of the possible configurations is invalid and if it is a cheap or expensive operation to check if a given configuration is valid? That would greatly affect the best way to generate a random valid configuration. – Bart van Ingen Schenau Mar 4 '17 at 9:02
• @BartvanIngenSchenau I can't, no. I haven't mapped out the requirements yet. – Smurfton Mar 4 '17 at 18:27

Sometimes the best way to generate a valid configuration is to make valid configurations and incrementally build larger ones.

I'm not familiar with La-Mulana. The first time I heard about it was around sixty seconds ago while reading your question. I'm going to assume the locations are linearly visited but we can perhaps generalize the below algorithm.

Assuming the locations are ordered A, B, C, and so forth, and for each X location we know that it requires items X1, X2 etc...:

1. Put all the items in location A (metaphorically speaking)
2. For the next location, figure out any items in the previous locations that could be moved to it (i.e. the items that are not needed before the present location). Randomly distribute those items between this location and the previous locations. (Random could mean 'to even out the levels', 'totally randomly' etc...)
3. Repeat (2) until you are at the last location

Depending on the particulars of La-Mulana, the above algorithm will need to be tweaked.

• Oh, sorry, no, the game isn't entirely linear; you can backtrack easily and there are branching paths. Progression typically involves solving puzzles or killing a boss to find new items/go to new places which allow you to solve further puzzles. – Smurfton Mar 3 '17 at 19:45
• Could you model it as a directed acyclic graph? If so, the above algorithm can be modified for that purpose. – Lan Mar 3 '17 at 19:52
• Yes, I can. At the moment I do plan on using this algorithm. – Smurfton Mar 3 '17 at 20:06

One approach that might work here is to create a mapping from integers to legal configurations. That is, 0 would be the first legal configuration, 1 would be the second legal configuration. Then it's simply a matter of generating a random number in a range and expanding that to a legal configuration.

The function that maps from a number to a configuration is the trick, of course. I'm not familiar with the rules of the game in question so it's not clear to me that this is a possible solution here or if it's worth the effort. A lot depends on how probable it is to generate an illegal configuration using the brute force method. If you provide a little more detail on the shape of the problem, more concrete advice should follow.

• I can't enumerate all the possible ways that make the game possible to complete; there are 107 items. – Smurfton Mar 3 '17 at 18:40
• @Smurfton You wouldn't need to. You'd just need a way of mapping the Nth logical item to that configuration. For example, if you have a lock that has 5 digits and you choose 4 numbers then you know that 57th combination would be 2-1-0-2 (that's just 57 in base 5) and you wouldn't need to actually generate the 56 combinations that came before it. You just need to come up with a good algorithm to determine "the Nth possible valid state of the game". – Servy Mar 3 '17 at 19:40