Say that we have a big list of tagged items, lets call this the pool:

const poolList = [[low, med], [low], [low], [low, med], [high, med]];

This list is often shuffled at runtime, and typically things I call stubs pool from this list. stubs just need to feature in one of the poolList for that item to be chosen.

const stubs = [[low], [low], [med], [high]];

For some better scene setting, let's imagine this is a quiz game where when the player encounters a "stub", they are then pointed to the corresponding item on the poolList.

Once an item is chosen, it is exhausted from the poolList. My issue is that I need to know whether or not my stubs could possibly exhaust all of the poolList by way of unfortunate overlapping/choices. So what I tried doing, to devise a way to test this, is to do a "worst case" run, with the definitions provided before, I am iterating over stubs. Note that its "worst" because I am trying to find poolList items that feature 2 or more items (if for example stub low chose the singular low item, then then we are happy, but there is no guarantee it would choose that as runtime is random!). And remember, choosing them exhausts them from the pool (the entire item is dumped out). Below is a "test" that will fail (which is what we want).

1. First stub is [low], I simply just choose [low, med] and remove that from the pool (that is the worst choice I can make)
2. Another [low], grab [low, med]
3. [med] grab the last item [high, med]
4. uh oh, [high] is not on the poolList, panic!

However, as I mentioned before, the poolList is variable and always random. Here is an example where my "test" would be flaky (well, flakier than usual)

Given:

const badPoolList = [
  [low, med],
  [low, high],
  [wc, med],
  [high, med]
];

If we start iterating this in order, choosing the worst options possible, it's apparent that when I hit the stub med, I will have 2 "worst" choices to choose from (because the list will always come in shuffled). So there is a chance that sometimes we end with a success, and sometimes with a failure (ie, poolList does not contain the item we want), depending on order.

I've scratched a sort of "test bed" with some ideas on how to solve this here: https://codepen.io/parthianshotgun/pen/JjBoxQv

However I find myself reaching for permutation or heaps algorithm, but that seems crazy since I would be doing n! iterations just to find the "one bad choice" that leads us to an exhausted pool. I wonder if I'm even framing this correctly, and am curious if there is a set theory/elegant way to weed out a faulty pool/stub combination.

CodePudding user response：

Maybe two solutions, both of which I think are inelegant come to mind:

1. To determine if the poolList can ever be exhausted by virtue of its combinations (see badPoolList example above). I run Heaps algorithm on it, and then, in order, "choose" the first item that matched a stub. Doing so I can find when the thing fails, eventually. This is a factorial issue though, as the poolList grows, so does my run time and cost. I find this solution slightly inelegant but can't say why.

2. Impose an artificial heuristic. Make it so that poolList must ALWAYS have a paired single tag that matches to stubs. So no matter what, ignoring all overlapping etc, each stub needs a corresponding, single item. So for

const stubs = [[low], [low], [med], [high]];

I need my array to hold singly tagged items, at a minimum equal to the number of stubs

const poolList = [[low, med], [low], [low], [med], [high], [low, med], [high, med]];

This will ensure that even in the worst of worst cases, we never run out of pooledItems to draw from, no matter the combinations.

CodePudding user response：

What I understood so far:

If you generated stub from the poolList, it means that at the initial state every element in stub should be present in poolList as there was no matching/depliting yet.

Now you start to match and deplete.

Say, you found the first element from stub in the poolList and you deleted this element from poolList. With that element you also deleted some other element that was paired with (overlapping) the first one.

Next you want to match another element from stab which happens to be the one that was paired and removed along with the first one you removed from the poolList.

Possible solution:

What you can do is maintain the frequency of the values in the poolList.

Initial state of poolList:

const badPoolList = [
  [low, med],
  [low, high],
  [high, med]
  [wc, med],
];

The frequency array or hashtable:

freq = [
"low": 2,
"med": 3,
"wc": 1,
"high": 1
];

Now, suppose you have a stub:

const stubs = [[low], [low], [med], [high]];

1. First element to match is "low".
2. We look at the frequency table and see that we have 2 of them (> 0).

If > 0 then deplete first match [low, med].

const badPoolList = [
  [low, high],
  [high, med]
  [wc, med],
];

Update frequency table:

freq = [
"low": 1, // Decrease this one
"med": 2, // AND this one was paired, so decreasing it 
"wc": 1,
"high": 2
];

Repeat for second match:

1. Second element to match is "low".
2. We look at the frequency table and see that we have 1 of them (> 0).

If > 0 then deplete first match [low, high].

const badPoolList = [
  [high, med]
  [wc, med],
];

Update frequency table:

freq = [
"low": 0, // Decrease this one
"med": 2,
"wc": 1,
"high": 1 // AND this one is also decreased
];

Repeat for third match:

1. Third element to match is "med".
2. We look at the frequency table and see that we have 2 of them (> 0).

If > 0 then deplete first match [high, med].

const badPoolList = [
  [wc, med],
];

Update frequency table:

freq = [
"low": 0,
"med": 1, // This one is decreased
"wc": 1,
"high": 0 // AND this one is also decreased
];

Repeat for fourth match:

1. Fourth element to match is "high".
2. We look at the frequency table and see that we have 0 of them.

Becuase our requency table looks like this:

freq = [
"low": 0,
"med": 1,
"wc": 1,
"high": 0 // IS 0
];

We know for sure there is no more highs left.

That's how you know if your stub is good or bad.