Recommend
5 
 Thumb up
 Hide
53 Posts
1 , 2 , 3  Next »   | 

BoardGameGeek» Forums » Board Game Design » Board Game Design

Subject: Help with Permutations rss

Your Tags: Add tags
Popular Tags: [View All]
Oliver Kiley
United States
Ann Arbor
Michigan
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
Okay, I’m working on another game design and am in need of some math support to develop some permutations. Here’s the situation:

I have 6 things, which we will call A, B, C, D, E, and F. These things will appear on playing cards in two pairs. The first set of pairs is easy, as follows, and you can see it encompasses all combinations, ignoring same letter ones (i.e. no A-A pairs):

A-B
A-C
A-D
A-E
A-F
B-A
B-C
B-D
B-E
B-F
C-A
C-B
C-D
C-E
C-F
D-A
D-B
D-C
D-E
D-F
E-A
E-B
E-C
E-D
E-F
F-A
F-B
F-C
F-D
F-E

So that’s 30 combinations. The second pair of 30 gets matched with this set, is much trickier, and this is where I need help.

The second pair needs to be arranged so that the first letter of the first pair (from above list) doesn’t appear at all in the second pair, and that the other 5 letters are used equally but with no duplicates across the double-pairing. For example, for the A set (first five from above) it could look like this:

A-B---C-D
A-C---B-E
A-D---E-F
A-E---F-D
A-F---D-C

So in the example above, there are no "A"s used except in the first column, there are no repeats across a row, and each letter only appears once in each column (except of course for the first column).

Remember too, that the frequencies need to be preserved across the whole scheme too, with each letter appearing exactly 5 times in a particular column of the entire pairing scheme.

I’ve gone blindly through the assignments a number of times, but it always breaks down somewhere and I end up with duplicates letters. I can probably figure it out via trial-and-error, but I’m hoping someone has a systematic way of doing this. Of course, it might be that there isn’t a solution! But I don’t think that’s the case.

Any help would be tremendous!
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
DC
United States
Grand Rapids
Michigan
flag msg tools
badge
Avatar
mbmbmb
Is it acceptable to have the same pairs paired more than once?

For example:

A-B---C-D
B-A---D-C

Although the order is different, the same 4 numbers appear together. Is that OK, or will that cause some bits of your state space to get lost?
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Sturv Tafvherd
United States
North Carolina
flag msg tools
mbmbmbmbmb
Mezmorki wrote:
... and each letter only appears once in each column (except of course for the first column).


That's a rather weird requirement, and that's probably why you're having some difficulties.

Given a "first pair" of A-B, you're left with C,D,E,F for the second pair. The moment you choose C-D as a second pair, you've basically eliminated C-E and C-F. Which pretty much begs the question: aside from alphabetical order, why would you choose C-D rather than C-E or C-F ?

I think answering that question will lead to an algorithm that answers your issue.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Bradley Eng-Kohn
United States
Poughkeepsie
New York
flag msg tools
Lost Gamer
badge
I want to live here
Avatar
mbmbmbmbmb
Since order does matter, your first set was 6 x 5 = 30, as you said.

Based on your description, that doesn't change with the next set.

(6 x 5) x (3 choose 2, order matters)=
30 x (3 x 2) =
30 x 6 =
180
3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Oliver Kiley
United States
Ann Arbor
Michigan
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
Stormtower wrote:
Mezmorki wrote:
... and each letter only appears once in each column (except of course for the first column).


That's a rather weird requirement, and that's probably why you're having some difficulties.

Given a "first pair" of A-B, you're left with C,D,E,F for the second pair. The moment you choose C-D as a second pair, you've basically eliminated C-E and C-F. Which pretty much begs the question: aside from alphabetical order, why would you choose C-D rather than C-E or C-F ?

I think answering that question will lead to an algorithm that answers your issue.


I should say each letter only appears once in each column of a particular letter set. So if C-D is used in pair two of the A-set, then C-E, C-F, C-B, and C-A would be used in one of the other sets somewhere.

I feel like there are has to be a way to start assining the second pairs in some sort of "inverse" way fits the criteria. As below, there are a lot of potential combinations, so it seems like there should be a few different solution that fit the criteria.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Scott Slomiany
United States
Unspecified
Unspecified
flag msg tools
designer
Avatar
mbmbmbmbmb
I'm not sure what you are looking for. if what you want to find is the odds of any specific 2card + 2card set out of six cards, the basic math would be something like this:

1st card draw: (you have 2 chances of drawing either of the two desired cards)

2/6

2nd card draw (you only have one chance to draw the remaining card that you want out of the cards that are left over)

2/6 * 1/5

3rd card draw: (you can now draw 1 of the two remaining cards that you want again)

2/6 * 1/5 * 2/4

4th card draw: (you are looking to draw the remaining target card out of the remaining three)

2/6 * 1/5 * 2/4 * 1/3

Soooo.....you final probability would be: .01111 of drawing any particular 4 cards into 2 sets of 2 cards out of your six card deck.

"invert" that prob, and you get: 1/.01111 = 90. Which means that 1 in 90 "draws" you will get your target card set. So this would mean that you have 90 different card combinations.

SOooooo, in the this example, you have a 1 in 90 chance of drawing, say:

AB and CD, or
ED and BC, or
FA and CD, or

Whatever specific combinations you are looking for.

2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Oliver Kiley
United States
Ann Arbor
Michigan
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
ghostOfChristmas wrote:
I'm not sure what you are looking for. if what you want to find is the odds of any specific 2card + 2card set out of six cards, the basic math would be something like this:

...

Whatever specific combinations you are looking for.


I'm not really concerned about draw probabilities at this point, I'm just looking for an equal distribution of items without repeating letters in the two-pair sets. The whole thing should be constrained down to 30 total cards, so I don't need every combination, I just need a scheme with equal distribution.

 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Sturv Tafvherd
United States
North Carolina
flag msg tools
mbmbmbmbmb
bengkohn wrote:
Since order does matter, your first set was 6 x 5 = 30, as you said.

Based on your description, that doesn't change with the next set.

(6 x 5) x (3 choose 2, order matters)=
30 x (3 x 2) =
30 x 6 =
180


That was my gut reaction too. But the OP specified "... and each letter only appears once in each column (except of course for the first column)." Which he has clarified later on.

So, like I had already said, if AB-CD is already in the results, you can't include AB-CE or AB-CF (because C has to be unique in that column for the subset that begins with A)

And if you have AB-CD, you won't be able to include AC-BD or AE-BD or AF-BD (because D has to be unique in that column for the subset that begins with A).

I haven't tried enumerating the list, but it seems to be a lot smaller than 180.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Sturv Tafvherd
United States
North Carolina
flag msg tools
mbmbmbmbmb
Mezmorki wrote:
I'm just looking for an equal distribution of items without repeating letters in the two-pair sets. The whole thing should be constrained down to 30 total cards, so I don't need every combination, I just need a scheme with equal distribution.



Aha, I wasn't paying attention to this part: The 30 letter-pairs are on individual cards. So you're basically just looking for pairings of those 30 cards that would fit the criteria you specified.

Right?
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Oliver Kiley
United States
Ann Arbor
Michigan
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
As an example, here was a run through:

A-B---F-E
A-C---E-D
A-D---C-F
A-E---B-C
A-F---D-B

B-A---F-D
B-C---E-F
B-D---C-E
B-E---B-A
B-F---A-C

C-A---F-B
C-B---E-A
C-D---B-F
C-E---A-D
C-F---D-E

D-A---F-C
D-B---C-A
D-C---B-E
D-E---A-F
D-F---E-B

E-A---D-F
E-B---A-E
E-C---F-A
E-D---C-B
E-F---B-D

F-A---
F-B---
F-C---
F-D---
F-E---


Everything fits up until the F-set .... the five combinations below are what are unassigned from the second set, but I can't assign them all to the F-set beause there are multiple D's in a column and multiple C's in a column.

------A-B
------C-D
------D-A
------D-C
------E-C
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Oliver Kiley
United States
Ann Arbor
Michigan
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
Stormtower wrote:
Mezmorki wrote:
I'm just looking for an equal distribution of items without repeating letters in the two-pair sets. The whole thing should be constrained down to 30 total cards, so I don't need every combination, I just need a scheme with equal distribution.



Aha, I wasn't paying attention to this part: The 30 letter-pairs are on individual cards. So you're basically just looking for pairings of those 30 cards that would fit the criteria you specified.

Right?


Yes.

Imagine you had two identicle sets of 30-cards each with 1 combination. The task is pairing up 1 card from each set so that there aren't any duplicated letters across the double-pair.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Evil Roy
United Kingdom
Sutton
Surrey
flag msg tools
Avatar
mbmbmbmbmb
Is this what you're looking for?

A-B ... C-D
A-C ... D-E
A-D ... E-F
A-E ... F-B
A-F ... B-C

B-C ... D-E
B-D ... E-F
B-E ... F-A
B-F ... A-C
B-A ... C-D

C-D ... E-F
C-E ... F-A
C-F ... A-B
C-A ... B-D
C-B ... D-E

D-E ... F-A
D-F ... A-B
D-A ... B-C
D-B ... C-E
D-C ... E-F

E-F ... A-B
E-A ... B-C
E-B ... C-D
E-C ... D-F
E-D ... F-A

F-A ... B-C
F-B ... C-D
F-C ... D-E
F-D ... E-A
F-E ... A-B
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Sturv Tafvherd
United States
North Carolina
flag msg tools
mbmbmbmbmb
Correct me if I'm wrong ... but rules violations marked in red

Mezmorki wrote:
As an example, here was a run through:

A-B---F-E
A-C---E-D
A-D---C-F
A-E---B-C
A-F---D-B

B-A---F-D
B-C---E-F
B-D---C-E
B-E---B-A (should be D-A)
B-F---A-C

C-A---F-B
C-B---E-A
C-D---B-F
C-E---A-D
C-F---D-E

D-A---F-C
D-B---C-A
D-C---B-E
D-E---A-F
D-F---E-B

E-A---D-F
E-B---A-E (should be A-C... but it's used with B-F already?)
E-C---F-A
E-D---C-B
E-F---B-D

F-A---
F-B---
F-C---
F-D---
F-E---


Everything fits up until the F-set .... the five combinations below are what are unassigned from the second set, but I can't assign them all to the F-set beause there are multiple D's in a column and multiple C's in a column.

------A-B
------C-D
------D-A this is now B-A)
------D-C
------E-C



edit ... it does look like once certain decisions are made on some pairings, you'll end up with a unique one-card-paired-with a second card...

Wait ... I wonder if that's the key ... symmetry. Once you paired AB to FE, then FE should also be paired to AB.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Sturv Tafvherd
United States
North Carolina
flag msg tools
mbmbmbmbmb
Evil Roy wrote:
Is this what you're looking for?

A-B ... C-D
A-C ... D-E
A-D ... E-F
A-E ... F-B
A-F ... B-C

B-C ... D-E
B-D ... E-F
B-E ... F-A
B-F ... A-C
B-A ... C-D

C-D ... E-F
C-E ... F-A
C-F ... A-B
C-A ... B-D
C-B ... D-E

D-E ... F-A
D-F ... A-B
D-A ... B-C
D-B ... C-E
D-C ... E-F

E-F ... A-B
E-A ... B-C
E-B ... C-D
E-C ... D-F
E-D ... F-A

F-A ... B-C
F-B ... C-D
F-C ... D-E
F-D ... E-A
F-E ... A-B


If I understand Mezmorki right, he wants every card paired up just once.

So pairing up (for example) the A-B card to C-F, D-F, E-F, F-E wouldn't be valid.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Oliver Kiley
United States
Ann Arbor
Michigan
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
Stormtower wrote:

If I understand Mezmorki right, he wants every card paired up just once.

So pairing up (for example) the A-B card to C-F, D-F, E-F, F-E wouldn't be valid.


Correct
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Brian Korreck
United States
Crystal Lake
Illinois
flag msg tools
badge
Avatar
mbmbmbmbmb
Guessing form these posts, I'd guess this was a DNA-sequencing game?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Rick
United States
Savage
Minnesota
flag msg tools
badge
Avatar
mbmbmb
So are you trying to make 30 cards total, each with 4 letters on them?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Oliver Kiley
United States
Ann Arbor
Michigan
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
hqbwk wrote:
Guessing form these posts, I'd guess this was a DNA-sequencing game?


No, but that's a great thematic idea!


RiffRaff14 wrote:
So are you trying to make 30 cards total, each with 4 letters on them?


Yes.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Rick
United States
Savage
Minnesota
flag msg tools
badge
Avatar
mbmbmb
Here is the diagram that shows all the possible combinations allowed (360 pairings of cards). You could use that to help maybe... plus I had fun making it.
3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Rick
United States
Savage
Minnesota
flag msg tools
badge
Avatar
mbmbmb
Mezmorki wrote:
RiffRaff14 wrote:
So are you trying to make 30 cards total, each with 4 letters on them?
Yes.
So it's the subset of 6 Pick 4 that has a uniform distribution of each of the letters. There's got to be easy math for that out there somewhere.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Oliver Kiley
United States
Ann Arbor
Michigan
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
Trial and error method:

A-B---F-E
A-C---E-D
A-D---C-B
A-E---B-F
A-F---D-C
B-A---D-F
B-C---E-A
B-D---C-E
B-E---A-C
B-F---F-D
C-A---E-F
C-B---F-A
C-D---A-E
C-E---D-B
C-F---B-D
D-A---A-F
D-B---F-C
D-C---E-B
D-E---C-A
D-F---B-E
E-A---B-C
E-B---C-F
E-C---A-D
E-D---F-B
E-F---D-A
F-A---C-D
F-B---E-C
F-C---D-E
F-D---B-A
F-E---A-B

I think this works ... except now I'm getting picky. The red numbers contain the opposite pairings within the same set. Not a huge deal perhaps, but lacks symetry and eveness in its distribution.

Grrr....
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
DC
United States
Grand Rapids
Michigan
flag msg tools
badge
Avatar
mbmbmb
RiffRaff14 wrote:
Mezmorki wrote:
RiffRaff14 wrote:
So are you trying to make 30 cards total, each with 4 letters on them?
Yes.
So it's the subset of 6 Pick 4 that has a uniform distribution of each of the letters. There's got to be easy math for that out there somewhere.


I'm sure that there is! The order requirement that's making this problem hard for me. I can do all sorts of things with unordered sets. Working on it...
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
United States
flag msg tools
mb
Here's an idea. I don't have the time right now to completely follow through this idea and see if I can make it work.

Give each letter a "buddy." So for example:

A -- F
B -- E
C -- D

Now, for each initial pair, pick the other pair by grabbing the "buddies" of the letters in the initial pair. For example, if AB is the first pair, the second pair would be FE (the F is A's buddy and the E is B's buddy).

Continuing this way, you get...

AB-FE
AC-FD
AD-FC
AE-FB
AF-FA (this is where it breaks down, when the first pair are buddy letters)

BA-EF
BC-ED
BD-EC
BE-EB (breaks down again)
BF-EA

.
.
.


So I think this should work in all cases except when the initial pair of letters is a buddy pair. If you develop a different rule for these cases (like maybe a "backup buddy"), you can probably make this work. I'll look at it some more when I get a chance.




 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
David Sant
United States
Easton
Massachusetts
flag msg tools
Avatar
mbmbmbmbmb
Mezmorki wrote:
Trial and error method:

A-B---F-E
A-C---E-D
A-D---C-B
A-E---B-F
A-F---D-C
B-A---D-F
B-C---E-A
B-D---C-E
B-E---A-C
B-F---F-D
C-A---E-F
C-B---F-A
C-D---A-E
C-E---D-B
C-F---B-D
D-A---A-F
D-B---F-C
D-C---E-B
D-E---C-A
D-F---B-E
E-A---B-C
E-B---C-F
E-C---A-D
E-D---F-B
E-F---D-A
F-A---C-D
F-B---E-C
F-C---D-E
F-D---B-A
F-E---A-B

I think this works ... except now I'm getting picky. The red numbers contain the opposite pairings within the same set. Not a huge deal perhaps, but lacks symetry and eveness in its distribution.

Grrr....


thought those (bolded) were illegal combos?
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
DC
United States
Grand Rapids
Michigan
flag msg tools
badge
Avatar
mbmbmb
Mezmorki, is the following an accurate re-statement of your problem?

You're looking for 30 ordered lists [w,x,y,z] with the following properties:

* w, x, y, z are each one of A, B, C, D, E, F, and are all distinct (no repeats)
* Each symbol must appear 5 times per position (so, 5 of the lists have A in the w spot, 5 have B in the w spot, 5 have A in the x spot, etc.).
* Each ordered pair must appear AT MOST one time in all 30 lists. For example, if [A,?,B,?] appears once, NO other list may ever have [A,*,B,*] no matter what the ?'s or *'s are. Similarly, if [?,?,C,D] appears, NO other list may ever contain [*,*,C,D] with C and D in those positions.

Is that right? Did I miss anything? Or, is it overly restrictive?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
1 , 2 , 3  Next »   | 
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.