100 choose 10, with an additional condition

I started a small project to try and learn a few new concepts (hopefully in C ++ or Python) and I was just hoping for a little help getting my idea started.

* This is all related to a larger basketball fantasy project, but I have to start somewhere.

I want 100 variables (players) and find every combination of 10 that satisfies a different condition.

For example; I have 100 players and I want to know how many combinations out of 10 (no duplicates and no order matters (so ABC == CBA) will match for a certain value (170 points between 10) or higher.

I'm assuming there is a Python library to handle this magic for me (which I'd like to know about), but I'm actually more interested in how I would go about doing this with C ++.

Thanks for any answers.


source to share

3 answers

Here are some psuedo-code

function player_combos(array players, int minimum_total) {
  array result = []
  players = sort(players, metric=most points first)
  int total = 0
  for p1 in 0 .. length(players) {
    if players[p1].points*10 < minimum_total - total:
    total += players[p1].points
    for p2 in p1+1 .. length(players) {
      if players[p2].points*9 < minimum_total - total:
      total += players[p2].points
      for p3 in p2+1 .. length(players) {
        if players[p3].points*8 < minimum_total - total:
        total += players[p3].points
        # continue these nested loops up to p10
                    for p10 in p9+1 .. length(players):
                      if players[p10].points < mininum_total - total:
                      # this is a valid combination
                      result.append((p1, p2, p3, p4, p5, p6, p7, p8, p9, p10))
        # remember to decrement total when we finish a loop iteration
        total -= players[p3].points
      total -= players[p2].points
    total -= players[p1].points
  return result


The idea here is that since you have the players sorted first, anytime you loop over the players in the list, all players afterwards should have an equal or lower total as the current player. This allows you to exit the current loop if the players' current points multiplied by the number of remaining spots left on the team are less than the number of points required to reach the minimum.

For example, you currently have four players on a team with a total of 80 points, which means you have 90 points left to hit the minimum and 6 spots left. The absolute minimum points your next player can get is 15 (from 90/6 == 15), so once you reach a player in the next cycle who has 14 or fewer points, you can exit that cycle.

This should drastically reduce the total number of combinations you need to get, as long as the minimum_total metric is set high enough.



Sounds like a derivative of SUBSET SUM (with a fixed size SUBSET), which turns out to be NP-Complete, Perhaps you can find help here: Optimizing the implementation of a subset of sums



I would just filter your list for all players with the required attributes and then loop through the filter list for all combinations.

Given your limitations, you should be able to use a simple (if deeply) nested loop.



All Articles