Feature Request: Choice Removal

[hiendv]

Hi, First of all, thanks for your great library. Do you accept feature request? It would be great for Chooser to have a method or an option to remove already picked items. Would you consider this to be on your roadmap? Thank you.

[mroth]

Thanks @hiendv for the suggestion. I unfortunately don't believe this is possible, as the algorithm used relies on pregenerating the weights to optimize for a constant selection time. Removing a Choice would currently require more or less regenerating from scratch, which would be equivalent to just creating a new Chooser.

I'm going to close this for now as not possible. However, if you know of a way to efficiently handle this algorithmically I am unaware of; please feel free to re-open and document. Thanks!

[ThinkChaos]

I'm also interested in such a feature.

For the algorithm, indeed no way around adjusting the scores, but I'd argue it's still better than the alternative if you take into account the whole picture.

Here's some incomplete code to illustrate that:

func pickRandom[T any](allChoices []T, nToPick int) []T { // my actual code is not generic, but the type doesn't matter here
    if nToPick > len(allChoices) {
        panic(fmt.Errorf("can't choose random weighted items: want %d but only have %d", nToPick, len(allChoices)))
    }

    if nToPick == len(allChoices) {
        return allChoices
    }

    choices := computeWeights(allChoices) // implementation elided
    picked := make([]T, 0, nToPick)

    for {
        c, err := weightedrand.NewChooser(choices...)
        if err != nil {
            panic(fmt.Errorf("can't choose random weighted item: %w", err))
        }

        choice := c.Pick()

        picked = append(picked, choice)
        if len(picked) == nToPick {
            return picked
        }

        // no need to check for -1: we're sure the item exists
        idx := slices.IndexFunc(choices, func(c weightedrand.Choice[T, uint]) bool {
            return c.Item == choice
        })

        choices = slices.Delete(choices, idx, idx+1)
    }
}

With a tweak to your module, we could save the loop slices.IndexFunc does: internally Pick knows the chosen index and can delete it directly.
I see two possible changes to achieve this:

• change/add an alternate Pick to also return the index of the chosen item
• add a Pop which does the Pick + delete directly

One extra question the second choice brings up is "What happens when you pop the last item?" Pick's return value is not designed to support "no item". I think making it panic is a decent solution since if you're using Pop and Pick, we can just document it's the caller's responsibility to be sure there's enough items. And using both those methods seems unlikely.
The Pop method could return (T, bool), just like a map.