Logic/Math exercise to determine all potential combinations that meet certain parameters

bficky · September 2016

I'm sure there's a math/logical approach to this question, but I'm having trouble figuring out the most systematic approach:

Say I have 10 groups (A through J) and 10 positions for these groups (0-9). The groups need to be sorted into a position, and two groups can't share a position. In addition, there are certain combinations that are not allowed (A6, A7, & A8 are not allowed; B2, B4, & B6, are not allowed, etc.).

Through trial and error, I've found an order of the groups that works, but I'm curious if there's a way to see all possible group/order combinations (assuming that the number of combinations isn't ridiculously big). I don't really have any computer skills to try and create a program or something to do this, so I'm actually using Excel to map this out in a 10x10 grid. However, it's tedious and unscientific to rearrange the groups into different options, and I was curious if anyone knew how I could take a more systematic approach I could take.

(If you want to see specifically what ridiculously dorky thing I'm trying to accomplish with this exercise, see below.)

OK, now that I'm safely hidden behind this spoiler tag, this is about Skylanders.

My son is really into Skylanders and is super hyped for the new game, where you can create you own skylanders in-game, as long as you have a plastic crystal toy to store them in. In Skylanders, there are 10 different elements (fire, water, air, etc.) and the created skylanders can be one of 10 different classes (sorcerer, knight, ninja, etc.). I've let him know that we're only going to get 10 of the crystals (one of each element) that you use to store your created skylander. Easy right, just make sure we never duplicate a class on two different elements, and we'll get all 10 classes and all 10 elements represented in the 10 crystals I'm willing to buy him.

However, the game also has other premade skylanders available, and their element & class are already known (for example, Wild Storm is an Air Knight). Ideally, we wouldn't want to create a skylander that is the same combination as a premade one... that's where the "unallowed" combinations come in.

Here's a screenshot of my manual approach to this:

In order to easily make sure all elements/classes were represented, I locked in the class columns and was rearranging the order of the element rows so that there was not a premade character in a star place (representing the 10 user created characters). The example above works, and it's easy to see that others would work as well (for example, flip-flop Fire and Light in order to change the Fire Brawler to a Fire Sorcerer). Of course, this is all for my son, who will certainly want the final say on which characters he'll make ("Tech Knight sounds dumb, I want to make an Undead Knight").

The number of acceptable combinations may be astronomical and it may just be easier to let him take his first pass on combinations and step in if/when a duplicate combo happens. However, it seemed like a fun and hopefully doable exercise to try and determine all the possible element/class options available.

tinwhiskers · September 2016

Not easily that I can see just because the criteria for allowing or not allowing a pairing is essentially arbitrary. Not avoiding the premades gives you 10!(10*9*8*7*6*5*4*3*2*1) non overlapping permutations.

To do it fast and dirty in a program, I'd generate a list of all possible strings So like what you have stared would be A0B1C2D3E4F5G6H7I8J9 and then just run through the list and remove anything that doesn't contain all 10 numbers and all 10 letters(actually this would be best to do when generating the list). Which gives you a set 10! permutations to work with 3,628,800 choices.

Then just run through that list and purge anything that contains your array of premade options {A3,A7,A9,B4.....J8}.

Aioua · September 2016

Naively, an upper bound for acceptable combinations is going to be 8! (the most choices of any element is 8, and every subsequent element has at least 1 less) which is 40,320.

But I suspect there are less combination than that. This is a combinatorics problem which is something I don't really have any knowledge on. I'm bored tho so I might write something to brute force it.

EDITL: Oh hmm no you could have 8 and then 8... I'm pretty sure the total number is still lower than 40k

Savant · September 2016

I think there's a way to remove the disallowed permutations for counting purposes, but it isn't especially straightforward, and messier the more disallowed ones you have. It is pretty easy to count the number of disallowed permutations for one restricted pair, say (A,1), and then subtract that out from the total number of permutations, but with multiple restricted pairs you'll potentially have overlapping permutations that you'll subtract out multiple times if you naively try to just subtract all of them from the total number of permutations without disallowed pairs. But some of the disallowed pairs could potentially have no overlap altogether, like (A, 1) and (A, 3) being disallowed.

The inclusion-exclusion principle, or some variation, might cover this. The more you add restrictions, the longer the list of additions and subtractions becomes.

Edit: oh, you want to generate the whole list? Yeah, that's more effort, since you could have over 3 million possibilities depending upon the restrictions, as mentioned above. You'd really want to write a program to generate the list for you.

hsu · September 2016

If you have programming skills, this is a classic use of the backtracking algorithm.
https://en.wikipedia.org/wiki/Backtracking

Daenris · September 2016

through a brute force method, I believe there are 134,820 possible combinations that obey your restrictions.

here's the R code I used

classes = LETTERS[1:10]
#elements are the positions 1 through 10
library(gtools)

p = permutations(10,10,classes)
dim(p)

disallowed = list()
disallowed[[1]] = c(4,8,10)
disallowed[[2]] = c(5,6,7,9)
disallowed[[3]] = c(6,7,9)
disallowed[[4]] = c(5,6,7)
disallowed[[5]] = c(2,8,10)
disallowed[[6]] = c(4,5)
disallowed[[7]] = c(1,3,9)
disallowed[[8]] = c(1,3,10)
disallowed[[9]] = c(1,10)
disallowed[[10]] = c(2,5,8)

bad.idx = rep(0,nrow(p))

for (i in 1:length(classes)) {
  d = disallowed[[i]]
  tmp = p[,d]
  bad.idx = bad.idx + rowSums(tmp==classes[i])  
}

p.reduced = p[bad.idx==0,]

It uses position to represent element, and the value of the position to represent class. Then it generates all possible permutations of 10 items in 10 spaces (3,628,800 as mentioned above). Then I set the disallowed positions for each class. I loop over the classes, and for each one I find any rows that have that class in a disallowed position, and just store it as a running sum in bad.idx. Finally, after the loop it reduces the permutation matrix by only grabbing those rows where there were never any disallowed class/element combinations. Leaving 134,820 rows in p.reduced.

furbat · September 2016

This is essentially the same discrete mathematics problem as placing n non attacking rooks on a n by n chessboard with non empty spaces. So each row/ column represents an element/class and the position of a rook would represent the class/element combination of the crystal. Non attacking means that no two rooks share a row or column. The non empty positions represent the free characters.

My discrete textbook is in my classroom and I don't remember the solution to this problem though.

I feel like there isn't a trivial solution though just a process for determining it based on the non empty squares. So I'd have to sit down and look at your solution and the solve it.

Smasher · September 2016

I independently brute forced the answer and got the same answer as @Daenris so I'm pretty sure that's right.

bficky · September 2016

Thank you all very much for the responses. I probably should have guessed that a small but manageable number of combinations was unlikely, and the actual answer would be either 0 (too many restrictions) or a huge number (too few). 134,820 possible combinations certainly fall on the huge number side. Since there are so many options that work, I'll just let my son choose whatever he wants and see if he can come up with one of those 134.820 options naturally.

My first thought on this, especially when creating the 10x10 grid, was the 8 queens question that I first encountered in The 7th Guest. In that one, I just kept playing with it until I found the answer, but I kinda figured a program could either brute force or heuristically get the answer. I took a basics of optimization and heuristics class in grad school, but I haven't needed to really use any of the little I learned in my engineering career.

Writing this exercise out and getting the responses does really make me wish that I knew at least the basics of programming so that I could tackle something like this myself. I know that there are tons of resources out there to self-teach the basics of programming, and this feels like the kick in the ass I needed to actually give it a shot. I understand the principles of how the solutions that you all presented work (10! for number of total options, then listing out all of the unallowed pairs that would invalidate an entire combination option), but I just didn't know the mechanics of how to tell a computer to do the actual number crunching.

Anyway, thanks again.

bficky · September 2016

OK, probably a dumb followup, but what if I wanted to rerun the lines of code that @Daenris posted with additional restrictions (like, maybe my son definitely doesn't want other element/class pairs)? I see that to add more additional restrictions, I'd just add more values to the c(x,x,x,x) portions of lines 9-18 and then the 134,820 will be reduced. But, once I've revised those lines, is there a simple (read: free and online) way to paste the lines of code into and actually get an output that contains the smaller list? Some code running program I need to actually to the process?

Again, asking how to run lines of code is probably a dumb question, but I'm both ignorant but also curious on the topic.

Smasher · October 2016

You can run the code I used on jsfiddle.net. A few notes:

* You'll need javascript enabled. All browsers do by default so that shouldn't be a problem unless you've disabled it for whatever reason.

* Because the number of combinations is potentially very large I don't try to list all of them; instead I randomly throw out whatever fraction of newly generated combinations I need in order to get approximately the right quantity. If you want to change that target quantity then modify maxDisplayedCombinations (currently at 100) in the settings variable at the very top.

* The script should automatically run and put its output in the lower right frame. If you want to make changes to the configuration (more on that in a second) you'll do that in the lower left frame. To regenerate the output (reflecting any changes you've made) press the "Run" button all the way in the top left corner of the page; even if you haven't changed anything this will result in different results due to the random number generator used by the code.

* You can change the list of element, classes, and preexisting combinations by changing the values returned by the getElements(), getClasses(), and getExistingCombinations() functions near the top of the code. Modifying these should be pretty straightforward if you just imitate the entries that are already there, but be sure you have all the brackets/commas/etc. in the right places or it can break your local copy of the script. If things go awry reloading the page should fix it.

Daenris · October 2016

Well my code is in R. I'm not aware of an online interpreter but R studio is a free GUI interface that you could install and run it in without too much difficulty. That said if you're interested in learning programming, I would suggest something more generally targeted like Python rather than R.

Penny Arcade

Quick Links

Logic/Math exercise to determine all potential combinations that meet certain parameters

Posts