## Generating permutations

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

SPACKlick
Posts: 195
Joined: Wed Apr 03, 2013 11:25 am UTC

### Generating permutations

I'm a relatively novice coder and can only really work in VB. I've been working on a maths problem for a while now relating to monopoly (for those interested it's an attempt to find the state the board can be in where every roll for a specific player and all players has the highest cost to that player). I'm stuck at one step. Distributing houses and hotels.

With 12 hotels and 32 houses over 22 properties there are 15 combinations of houses/hotels/blanks that work. These 15 combinations come in 1.43 E+10 permutations (of which many will be invalid by having a variance greater than 1 in each set.

What I can't work out is a way of looping through generating these specific permutations rather than the 1.12 E+21 total permutations. Each permutation needs to be checked for variance within a set which initially I was doing with a loop

For P3 = 0 to 5
for P4 = max(p3-1,0) to min(p3+1,5)
for p5 = max(p3-1,p4-1,0) to min(p3+1,p4+1,5)

but that can't be tailored to the 14 billion set rather than the sextillion set.

Xenomortis
Not actually a special flower.
Posts: 1426
Joined: Thu Oct 11, 2012 8:47 am UTC

### Re: Generating permutations

I don't understand the question.
But I'm pretty sure iterating through board states is not the way you're going to want to solve your problem.
If the problem is "what state of the board results in the worst possible turn for particular player", then a player can only reach 11 squares, the state of the rest of the board "almost" doesn't matter (utilities and train stations notwithstanding).

SPACKlick
Posts: 195
Joined: Wed Apr 03, 2013 11:25 am UTC

### Re: Generating permutations

Xenomortis wrote:I don't understand the question.
But I'm pretty sure iterating through board states is not the way you're going to want to solve your problem.
If the problem is "what state of the board results in the worst possible turn for particular player", then a player can only reach 11 squares, the state of the rest of the board "almost" doesn't matter (utilities and train stations notwithstanding).

That answers "what is the worst state the board can be in for a player for one turn" (which actually includes the 11 direct landings, plus the 66 double and roll and the 324 double double rolls as well as all the community chest and chance moving around the board cards.

The question is, is there a way of generating a subset of permutations for analysis without trimming them from a larger list of permutations.

In the gerenal case I have n values between 0 and 5 inclusive. The total of these values is 4n show all permutations.
The instinctive method is to go through all 5^n permutations identifying the tiny subset where the value is 4n.
I'm asking is there a general rule for generating this sort of permutation subset.

heatsink
Posts: 86
Joined: Fri Jun 30, 2006 8:58 am UTC

### Re: Generating permutations

I don't understand the Monopoly question. I don't understand why there are 15 possible property improvements, or what the variance of a set means when the set elements are property improvements.

This sounds like a constraint programming problem. The general rule to speed up a search is to formulate it in a way that parts of the search space can be excluded early on in the search. In constraint programming these techniques are called "consistency" and "constraint propagation." Consistency checking backtracks (like skipping a loop iterations) when a partial solution is invalid. Constraint propagation refines the search space (like computing smaller loop bounds) based on the choices made so far. Be aware that it's a large subject covering many kinds of problems, and lots of the techniques won't be applicable to the problem you're trying to solve.

SPACKlick
Posts: 195
Joined: Wed Apr 03, 2013 11:25 am UTC

### Re: Generating permutations

Thanks, that gives me somewhere to start at least. Thank you.

Sandor
Posts: 177
Joined: Sat Feb 13, 2010 8:25 am UTC

### Re: Generating permutations

heatsink wrote:I don't understand the Monopoly question. I don't understand why there are 15 possible property improvements, or what the variance of a set means when the set elements are property improvements.

For it to be the worst possible board for a given player, all available buildings are going to be on the board, and owned by someone else. Every property will have 1 hotel, or 4 houses, or 3 houses, or 2 houses, or 1 houses, or 0 houses on it. There are 22 properties. 12 hotels, and 32 houses. The 15 ways this can happen are:

Code: Select all

`12 hotel, 8*4-house + 0*3-house + 0*2-house + 0*1-house + 2*0-house = 32 houses, 20 developed properties12 hotel, 7*4-house + 1*3-house + 0*2-house + 1*1-house + 1*0-house = 32 houses, 21 developed properties12 hotel, 7*4-house + 0*3-house + 2*2-house + 0*1-house + 1*0-house = 32 houses, 21 developed properties12 hotel, 7*4-house + 0*3-house + 1*2-house + 2*1-house + 0*0-house = 32 houses, 22 developed properties12 hotel, 6*4-house + 2*3-house + 1*2-house + 0*1-house + 1*0-house = 32 houses, 21 developed properties12 hotel, 6*4-house + 2*3-house + 0*2-house + 2*1-house + 0*0-house = 32 houses, 22 developed properties12 hotel, 6*4-house + 1*3-house + 2*2-house + 1*1-house + 0*0-house = 32 houses, 22 developed properties12 hotel, 6*4-house + 0*3-house + 4*2-house + 0*1-house + 0*0-house = 32 houses, 22 developed properties12 hotel, 5*4-house + 4*3-house + 0*2-house + 0*1-house + 1*0-house = 32 houses, 21 developed properties12 hotel, 5*4-house + 3*3-house + 1*2-house + 1*1-house + 0*0-house = 32 houses, 22 developed properties12 hotel, 5*4-house + 2*3-house + 3*2-house + 0*1-house + 0*0-house = 32 houses, 22 developed properties12 hotel, 4*4-house + 5*3-house + 0*2-house + 1*1-house + 0*0-house = 32 houses, 22 developed properties12 hotel, 4*4-house + 4*3-house + 2*2-house + 0*1-house + 0*0-house = 32 houses, 22 developed properties12 hotel, 3*4-house + 6*3-house + 1*2-house + 0*1-house + 0*0-house = 32 houses, 22 developed properties12 hotel, 2*4-house + 8*3-house + 0*2-house + 0*1-house + 0*0-house = 32 houses, 22 developed properties`

Output generated by this C code:
Spoiler:

Code: Select all

`#include <stdio.h>#define PROPERTIES 22#define HOTELS 12#define HOUSES 32#define MAXHOUSEPROPS (PROPERTIES - HOTELS)int main(void){  /* Number of properties with hotels, and 4, 3, 2, 1 & 0 houses on them, respectively */  int houses[6];  houses[5] = HOTELS;  for (houses[4] = MAXHOUSEPROPS ; houses[4] >= 0 ; houses[4]--) {    for (houses[3] = MAXHOUSEPROPS ; houses[3] >= 0 ; houses[3]--) {      for (houses[2] = MAXHOUSEPROPS ; houses[2] >= 0 ; houses[2]--) {        for (houses[1] = MAXHOUSEPROPS ; houses[1] >= 0 ; houses[1]--) {          houses[0] = PROPERTIES - houses[5] - houses[4] - houses[3] - houses[2] - houses[1];          /* Can't have a negative number of blanks (i.e. more than developed 22 properties) */          if (houses[0] >= 0) {            /* Not using all houses is wasteful */            if (houses[4]*4 + houses[3]*3 + houses[2]*2 + houses[1] == HOUSES) {              printf("12 hotel, %d*4-house + %d*3-house + %d*2-house + %d*1-house + %d*0-house = "                     "%d houses, %d developed properties\n",                     houses[4], houses[3], houses[2], houses[1], houses[0],                     houses[4]*4 + houses[3]*3 + houses[2]*2 + houses[1],                     12 + houses[4] + houses[3] + houses[2] + houses[1]);            }          }        }      }    }  }  return 0;}`

The OP wants to generate all the permutations of these 15 combinations. The totals are:

Code: Select all

`22!/10!/12! * 10!/2!/8! = 2.90991e+07 permutations22!/10!/12! * 10!/3!/7! * 3!/2!/1! * 2!/1!/1! = 4.65585e+08 permutations22!/10!/12! * 10!/3!/7! * 3!/1!/2! = 2.32793e+08 permutations22!/10!/12! * 10!/3!/7! * 3!/2!/1! * 2!/0!/2! = 2.32793e+08 permutations22!/10!/12! * 10!/4!/6! * 4!/2!/2! * 2!/1!/1! = 1.62955e+09 permutations22!/10!/12! * 10!/4!/6! * 4!/2!/2! * 2!/0!/2! = 8.14774e+08 permutations22!/10!/12! * 10!/4!/6! * 4!/3!/1! * 3!/1!/2! * 1!/0!/1! = 1.62955e+09 permutations22!/10!/12! * 10!/4!/6! * 4!/0!/4! = 1.35796e+08 permutations22!/10!/12! * 10!/5!/5! * 5!/1!/4! = 8.14774e+08 permutations22!/10!/12! * 10!/5!/5! * 5!/2!/3! * 2!/1!/1! * 1!/0!/1! = 3.2591e+09 permutations22!/10!/12! * 10!/5!/5! * 5!/3!/2! * 3!/0!/3! = 1.62955e+09 permutations22!/10!/12! * 10!/6!/4! * 6!/1!/5! * 1!/0!/1! = 8.14774e+08 permutations22!/10!/12! * 10!/6!/4! * 6!/2!/4! * 2!/0!/2! = 2.03693e+09 permutations22!/10!/12! * 10!/7!/3! * 7!/1!/6! * 1!/0!/1! = 5.43183e+08 permutations22!/10!/12! * 10!/8!/2! * 8!/0!/8! = 2.90991e+07 permutationsTotal = 1.42973e+10 permutations`

Monopoly only allows a difference of one in the number of houses on each property in a set (hotels counting as 5 houses). A set of three properties, one with 4 houses, and the other two with a single house each is against the rules. This is what is meant by some permutations are "invalid by having a variance greater than 1 in each set".

At least, that's how I take it.

PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

### Re: Generating permutations

Sandor wrote:Monopoly only allows a difference of one in the number of houses on each property in a set (hotels counting as 5 houses). A set of three properties, one with 4 houses, and the other two with a single house each is against the rules. This is what is meant by some permutations are "invalid by having a variance greater than 1 in each set".

At least, that's how I take it.

If so only iterating through the possibilities fulfilling that rule shouldn't be particularily hard. How I would do it based on 5 minutes of thinking and little monopoly knowlegde since I can't stand that game: There are 8 groups in monopoly+ stations and utilities. With that rule for a group of 3 the group can have can have: 0-12 houses and 1 hotel/8 houses, 2 hotels/4 houses or 3 hotels. 16 possibilities. There are different internal ways to reach these possibilities but I guess (though I might be wrong) that you can determine the optimal way to distribute a set number of houses between 3 group members internally for the group without looking at the other groups. So do that for all 16 possibilities for all 8 groups and keep the results of course. Now go and combine the 16 possibilities with the possibilities for the other groups. 16^8=4294967296 which should be doable. But the number gets significantly lower if you only test the possibilities where you don't go over your maximum house or hotel number.

(One group consist of 4 and 2 groups of two but that doesn't change the numbers much.)

Though if you are just searching for the highest expected payout iterating is probably an inefficient way (though maybe easier to write and thus more efficient taking your time into account): Determine the probability for each field, determine the best way to distribute 0-12/0-3 hotels in each group taking into account the individual probabilities. Multiply the (payout with buildings) - (payout with 0 buildings) with the probability that the player lands there, add the three resulting numbers together to see how much more the the player is likely to spend if you invest x houses in the group. From that point you can probably determine the best way to distribute the houses without going through all options.