Skip to content

Instantly share code, notes, and snippets.

@geovanisouza92
Created November 25, 2016 12:28
Show Gist options
  • Save geovanisouza92/8cb5cb11d105d859569b8f60b4768b08 to your computer and use it in GitHub Desktop.
Save geovanisouza92/8cb5cb11d105d859569b8f60b4768b08 to your computer and use it in GitHub Desktop.
Lists generation problem
  • There are two kinds of items: A and B
  • Each item B could be replaced by A' and A"
  • Given a list with items A and B (the order is not important), generate the most quantity of target-lists only with items A, A' and A" below the time limit t
  • Each target-list is sorted after generation, so there isn't necessary to generate each permutation (only replacements are sufficient)
  • The source list have an arbitrary size
  • The number of unique possibilities is where n is the number of B items
  • A items doesn't need to be modified, so it could be reused

Given the source list:

[A, A, B, A, B]

These are the relevant target-lists:

[A, A, A', A, A']
[A, A, A", A, A']
[A, A, A", A, A"]

Notice the absence of [A, A, A', A, A"]: as the target list is ordered, this option is not relevant.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment