views:

771

answers:

2

I am trying to create an application that will calculate the cost of exotic parimutuel wager costs. I have found several for certain types of bets but never one that solves all the scenarios for a single bet type. If I could find an algorithm that could calculate all the possible combinations I could use that formula to solve my other problems.

Additional information: I need to calculate the permutations of groups of numbers. For instance;

Group 1 = 1,2,3
Group 2 = 2,3,4
Group 3 = 3,4,5

What are all the possible permutation for these 3 groups of numbers taking 1 number from each group per permutation. No repeats per permutation, meaning a number can not appear in more that 1 position. So 2,4,3 is valid but 2,4,4 is not valid.

Thanks for all the help.

+4  A: 

Like most interesting problems, your question has several solutions. The algorithm that I wrote (below) is the simplest thing that came to mind.

I found it easiest to think of the problem like a tree-search: The first group, the root, has a child for each number it contains, where each child is the second group. The second group has a third-group child for each number it contains, the third group has a fourth-group child for each number it contains, etc. All you have to do is find all valid paths from the root to leaves.

However, for many groups with lots of numbers this approach will prove to be slow without any heuristics. One thing you could do is sort the list of groups by group-size, smallest group first. That would be a fail-fast approach that would, in general, discover that a permutation isn't valid sooner than later. Look-ahead, arc-consistency, and backtracking are other things you might want to think about. [Sorry, I can only include one link because it's my first post, but you can find these things on Wikipedia.]

## Algorithm written in Python ##
## CodePad.org has a Python interpreter

Group1 = [1,2,3] ## Within itself, each group must be composed of unique numbers
Group2 = [2,3,4]
Group3 = [3,4,5]
Groups = [Group1,Group2,Group3] ## Must contain at least one Group

Permutations = [] ## List of valid permutations

def getPermutations(group, permSoFar, nextGroupIndex):
  for num in group:
    nextPermSoFar = list(permSoFar) ## Make a copy of the permSoFar list

    ## Only proceed if num isn't a repeat in nextPermSoFar
    if nextPermSoFar.count(num) == 0: 
      nextPermSoFar.append(num)  ## Add num to this copy of nextPermSoFar

      if nextGroupIndex != len(Groups): ## Call next group if there is one...
        getPermutations(Groups[nextGroupIndex], nextPermSoFar, nextGroupIndex + 1)
      else: ## ...or add the valid permutation to the list of permutations
        Permutations.append(nextPermSoFar)

## Call getPermutations with:
##  * the first group from the list of Groups
##  * an empty list
##  * the index of the second group
getPermutations(Groups[0], [], 1)

## print results of getPermutations
print 'There are', len(Permutations), 'valid permutations:'
print Permutations
the Will Cole
+1  A: 

AS a punter I can tell you there is a much simpler way:

For a trifecta, you need 3 combinations. Say there are 8 runners, the total number of possible permutations is 8 (total runners)* 7 (remaining runners after the winner omitted)* 6 (remaining runners after the winner and 2nd omitted) = 336

For an exacta (with 8 runners) 8 * 7 = 56

Quinellas are an exception, as you only need to take each bet once as 1/2 pays as well as 2/1 so the answer is 8*7/2 = 28

Simple

Grant