Jump to content
  • Advertisement
Sign in to follow this  
Durakken

Non-duplicating pairs from a set

This topic is 825 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

What I need is to generate a series of 6 pairs from a set of 13 numbers that over the course of a cycle of 13 generations do not repeat, but the cycle repeats all pairs in the same order. 

 

Explanation...

 

I'm trying to create a small algorithm to predict which portal opens to which world during what year.

There are 13 worlds

Portals open every 500 years

Worlds can only open portals to 1 other world at a time

Portals open between each other world, before they open to the same world again...

 

So let's say we're talking world 0...World 0 will open a portal in the following order...

0 to 1

0 to 2

0 to 3

0 to 4

0 to 5

0 to 6

0 to 7

0 to 8

0 to 9

0 to 10

0 to 11

0 to 12

0 to Nowhere

repeat

 

That's simple enough, but I'm completely lost when taking into acount all 13 worlds, when they're linked with each other, and when they're linked to nowhere.

 

I'm using Javascript with a simple document.write( world opens to world) format to see the output... I would post up what code I have but I'm so lost that it wouldn't help and is only really that so... yeah. Can someone please help.

Edited by Durakken

Share this post


Link to post
Share on other sites
Advertisement

Each world needs a list of other worlds it has already visited(a simple integer list would suffice). You can use this information to prevent it from opening a repeat portal before all other worlds have been visited. As for keeping track of who is "linked" to who, each world needs another integer number to represent who it is connected to.

 

Are there any restrictions not stated? Can world 0 be connected to 1 while 1 can connect to 2? Maybe elaborate a little bit more on the confusing part.

Share this post


Link to post
Share on other sites

Need to be elaborated more.

 

If it's 6 pairs from a set of 13 numbers, then one of the world won't have any portal at a given time, correct?

 

Gen 0, your set will look like this: [0,1], [2,3], [4,5], [6,7], [8,9],[10,11]

World 12 does not have a portal open.

 

Then, what's the rule for picking the next set?  Is it sequential?  Does this mean that world 0 will always be given the priority to pick the next world?  And World 12 will be lonely until the 12th generation.

 

Example:

Gen 1, set looks like this: [0,2], [1,3], [4,6], [5,7], [8,10], [9, 11].  In which case 12 is lonely again.

Gen 2, set looks like this: [0,3], [1,2], [4,7], [5,6], [8,11], [9, 10].  In which case 12 is lonely again.

 

Edit:

 

Here's a proposal.  Use a queue/stack depending on what order you want them to be, and each world needs to keep track a list of worlds that it has had a portal open to until next reset.  Initially your queue is just the sequence of the world.

 

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

 

Then, pop each world, if there's no world popped yet, keep this world 'open'.  Then pop the next world.  Attempt to link these two worlds together.  If two worlds have been linked together before, then it should fail the linking process, and you would have two worlds 'open'.  Repeat for the next world.  If pairing happens, "close"/"linked" both worlds.  Example:

 

Gen 0

 

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

Pop #0.  Open: [0], Queue: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

Pop #1.  Linked: [0, 1], Queue: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

Pop #2.  Linked: [0, 1], Open: [2], Queue: [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

and so on.. until the last one

Pop #11. Linked: [0,1], [2,3], [4,5], [6,7], [8,9], [10,11]. Queue: [12]

 

Gen 1

Reinserts all world back to the queue:

 

Queue: [12, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Pop #12.  Open: [12], Queue: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Pop #0.  Linked: [12, 0], Queue: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Pop #1.  Linked: [12, 0], Open: [1], Queue: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

and so on.. until the last one

Pop #10. Linked: [12,0], [1,2], [3,4], [5,6], [7,8], [9,10]. Queue: [11]

 

Gen 2

Reinserts all world back to the queue:

 

Queue: [11, 12, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Pop #11.  Open: [11], Queue: [12, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Pop #12.  Linked: [11, 12], Queue: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Pop #0.  Linked: [11, 12], Open: [0], Queue: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Pop #1.  Linked: [11, 12], Open: [0], Open [1], Queue: [2, 3, 4, 5, 6, 7, 8, 9, 10]  // since [0,1] has been linked before

and so on.. until the last one

Pop #9. Linked: [11, 12], [0,2], [1,3], [4,6], [5,7], [8,10]. Queue: [9]

 

Gen 3

Queue: [9, 11, 12, 0, 2, 1, 3, 4, 6, 5, 7, 8, 10]

Final Order: [9, 11], [12, 2], [0, 3], [1, 4], [6, 8], [5, 10], [7]

 

 

You can get different linking order by playing around with different insertion order.  I am using the ordering of pairs, you can keep it sequential.  You can also use a stack instead of a queue.  I am using a queue so that the world that didn't get a portal open from previous generation would always get one at the next generation.

 

-- More edit:

 

Here's a list of all the portals:

 

Gen: 0
Queue Before: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Linked: [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9], [10, 11]]
Queue After: [12]
Link History: {0=>[1], 1=>[0], 2=>[3], 3=>[2], 4=>[5], 5=>[4], 6=>[7], 7=>[6], 8=>[9], 9=>[8], 10=>[11], 11=>[10], 12=>[]}

Gen: 1
Queue Before: [12, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Linked: [[12, 0], [1, 2], [3, 4], [5, 6], [7, 8], [9, 10]]
Queue After: [11]
Link History: {0=>[1, 12], 1=>[0, 2], 2=>[3, 1], 3=>[2, 4], 4=>[5, 3], 5=>[4, 6], 6=>[7, 5], 7=>[6, 8], 8=>[9, 7], 9=>[8, 10], 10=>[11, 9], 11=>[10], 12=>[0]}

Gen: 2
Queue Before: [11, 12, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Linked: [[11, 12], [0, 2], [1, 3], [4, 6], [5, 7], [8, 10]]
Queue After: [9]
Link History: {0=>[1, 12, 2], 1=>[0, 2, 3], 2=>[3, 1, 0], 3=>[2, 4, 1], 4=>[5, 3, 6], 5=>[4, 6, 7], 6=>[7, 5, 4], 7=>[6, 8, 5], 8=>[9, 7, 10], 9=>[8, 10], 10=>[11, 9, 8], 11=>[10, 12], 12=>[0, 11]}

Gen: 3
Queue Before: [9, 11, 12, 0, 2, 1, 3, 4, 6, 5, 7, 8, 10]
Linked: [[9, 11], [12, 2], [0, 3], [1, 4], [6, 8], [5, 10]]
Queue After: [7]
Link History: {0=>[1, 12, 2, 3], 1=>[0, 2, 3, 4], 2=>[3, 1, 0, 12], 3=>[2, 4, 1, 0], 4=>[5, 3, 6, 1], 5=>[4, 6, 7, 10], 6=>[7, 5, 4, 8], 7=>[6, 8, 5], 8=>[9, 7, 10, 6], 9=>[8, 10, 11], 10=>[11, 9, 8, 5], 11=>[10, 12, 9], 12=>[0, 11, 2]}

Gen: 4
Queue Before: [7, 9, 11, 12, 2, 0, 3, 1, 4, 6, 8, 5, 10]
Linked: [[7, 9], [11, 2], [12, 3], [0, 4], [1, 6], [8, 5]]
Queue After: [10]
Link History: {0=>[1, 12, 2, 3, 4], 1=>[0, 2, 3, 4, 6], 2=>[3, 1, 0, 12, 11], 3=>[2, 4, 1, 0, 12], 4=>[5, 3, 6, 1, 0], 5=>[4, 6, 7, 10, 8], 6=>[7, 5, 4, 8, 1], 7=>[6, 8, 5, 9], 8=>[9, 7, 10, 6, 5], 9=>[8, 10, 11, 7], 10=>[11, 9, 8, 5], 11=>[10, 12, 9, 2], 12=>[0, 11, 2, 3]}

Gen: 5
Queue Before: [10, 7, 9, 11, 2, 12, 3, 0, 4, 1, 6, 8, 5]
Linked: [[10, 7], [9, 2], [11, 3], [12, 4], [0, 6], [1, 8]]
Queue After: [5]
Link History: {0=>[1, 12, 2, 3, 4, 6], 1=>[0, 2, 3, 4, 6, 8], 2=>[3, 1, 0, 12, 11, 9], 3=>[2, 4, 1, 0, 12, 11], 4=>[5, 3, 6, 1, 0, 12], 5=>[4, 6, 7, 10, 8], 6=>[7, 5, 4, 8, 1, 0], 7=>[6, 8, 5, 9, 10], 8=>[9, 7, 10, 6, 5, 1], 9=>[8, 10, 11, 7, 2], 10=>[11, 9, 8, 5, 7], 11=>[10, 12, 9, 2, 3], 12=>[0, 11, 2, 3, 4]}

Gen: 6
Queue Before: [5, 10, 7, 9, 2, 11, 3, 12, 4, 0, 6, 1, 8]
Linked: [[5, 9], [10, 2], [7, 11], [3, 6], [12, 1], [4, 8]]
Queue After: [0]
Link History: {0=>[1, 12, 2, 3, 4, 6], 1=>[0, 2, 3, 4, 6, 8, 12], 2=>[3, 1, 0, 12, 11, 9, 10], 3=>[2, 4, 1, 0, 12, 11, 6], 4=>[5, 3, 6, 1, 0, 12, 8], 5=>[4, 6, 7, 10, 8, 9], 6=>[7, 5, 4, 8, 1, 0, 3], 7=>[6, 8, 5, 9, 10, 11], 8=>[9, 7, 10, 6, 5, 1, 4], 9=>[8, 10, 11, 7, 2, 5], 10=>[11, 9, 8, 5, 7, 2], 11=>[10, 12, 9, 2, 3, 7], 12=>[0, 11, 2, 3, 4, 1]}

Gen: 7
Queue Before: [0, 5, 9, 10, 2, 7, 11, 3, 6, 12, 1, 4, 8]
Linked: [[0, 5], [2, 7], [9, 3], [10, 6], [11, 1], [12, 8]]
Queue After: [4]
Link History: {0=>[1, 12, 2, 3, 4, 6, 5], 1=>[0, 2, 3, 4, 6, 8, 12, 11], 2=>[3, 1, 0, 12, 11, 9, 10, 7], 3=>[2, 4, 1, 0, 12, 11, 6, 9], 4=>[5, 3, 6, 1, 0, 12, 8], 5=>[4, 6, 7, 10, 8, 9, 0], 6=>[7, 5, 4, 8, 1, 0, 3, 10], 7=>[6, 8, 5, 9, 10, 11, 2], 8=>[9, 7, 10, 6, 5, 1, 4, 12], 9=>[8, 10, 11, 7, 2, 5, 3], 10=>[11, 9, 8, 5, 7, 2, 6], 11=>[10, 12, 9, 2, 3, 7, 1], 12=>[0, 11, 2, 3, 4, 1, 8]}

Gen: 8
Queue Before: [4, 0, 5, 2, 7, 9, 3, 10, 6, 11, 1, 12, 8]
Linked: [[4, 2], [0, 7], [5, 3], [9, 6], [10, 1], [11, 8]]
Queue After: [12]
Link History: {0=>[1, 12, 2, 3, 4, 6, 5, 7], 1=>[0, 2, 3, 4, 6, 8, 12, 11, 10], 2=>[3, 1, 0, 12, 11, 9, 10, 7, 4], 3=>[2, 4, 1, 0, 12, 11, 6, 9, 5], 4=>[5, 3, 6, 1, 0, 12, 8, 2], 5=>[4, 6, 7, 10, 8, 9, 0, 3], 6=>[7, 5, 4, 8, 1, 0, 3, 10, 9], 7=>[6, 8, 5, 9, 10, 11, 2, 0], 8=>[9, 7, 10, 6, 5, 1, 4, 12, 11], 9=>[8, 10, 11, 7, 2, 5, 3, 6], 10=>[11, 9, 8, 5, 7, 2, 6, 1], 11=>[10, 12, 9, 2, 3, 7, 1, 8], 12=>[0, 11, 2, 3, 4, 1, 8]}

Gen: 9
Queue Before: [12, 4, 2, 0, 7, 5, 3, 9, 6, 10, 1, 11, 8]
Linked: [[12, 7], [2, 5], [4, 9], [0, 10], [6, 11], [3, 8]]
Queue After: [1]
Link History: {0=>[1, 12, 2, 3, 4, 6, 5, 7, 10], 1=>[0, 2, 3, 4, 6, 8, 12, 11, 10], 2=>[3, 1, 0, 12, 11, 9, 10, 7, 4, 5], 3=>[2, 4, 1, 0, 12, 11, 6, 9, 5, 8], 4=>[5, 3, 6, 1, 0, 12, 8, 2, 9], 5=>[4, 6, 7, 10, 8, 9, 0, 3, 2], 6=>[7, 5, 4, 8, 1, 0, 3, 10, 9, 11], 7=>[6, 8, 5, 9, 10, 11, 2, 0, 12], 8=>[9, 7, 10, 6, 5, 1, 4, 12, 11, 3], 9=>[8, 10, 11, 7, 2, 5, 3, 6, 4], 10=>[11, 9, 8, 5, 7, 2, 6, 1, 0], 11=>[10, 12, 9, 2, 3, 7, 1, 8, 6], 12=>[0, 11, 2, 3, 4, 1, 8, 7]}

Gen: 10
Queue Before: [1, 12, 7, 2, 5, 4, 9, 0, 10, 6, 11, 3, 8]
Linked: [[1, 7], [12, 5], [9, 0], [4, 10], [2, 6]]
Queue After: [11, 3, 8]
Link History: {0=>[1, 12, 2, 3, 4, 6, 5, 7, 10, 9], 1=>[0, 2, 3, 4, 6, 8, 12, 11, 10, 7], 2=>[3, 1, 0, 12, 11, 9, 10, 7, 4, 5, 6], 3=>[2, 4, 1, 0, 12, 11, 6, 9, 5, 8], 4=>[5, 3, 6, 1, 0, 12, 8, 2, 9, 10], 5=>[4, 6, 7, 10, 8, 9, 0, 3, 2, 12], 6=>[7, 5, 4, 8, 1, 0, 3, 10, 9, 11, 2], 7=>[6, 8, 5, 9, 10, 11, 2, 0, 12, 1], 8=>[9, 7, 10, 6, 5, 1, 4, 12, 11, 3], 9=>[8, 10, 11, 7, 2, 5, 3, 6, 4, 0], 10=>[11, 9, 8, 5, 7, 2, 6, 1, 0, 4], 11=>[10, 12, 9, 2, 3, 7, 1, 8, 6], 12=>[0, 11, 2, 3, 4, 1, 8, 7, 5]}

Gen: 11
Queue Before: [11, 3, 8, 1, 7, 12, 5, 9, 0, 4, 10, 2, 6]
Linked: [[3, 7], [11, 5], [1, 9], [8, 0], [12, 10]]
Queue After: [4, 2, 6]
Link History: {0=>[1, 12, 2, 3, 4, 6, 5, 7, 10, 9, 8], 1=>[0, 2, 3, 4, 6, 8, 12, 11, 10, 7, 9], 2=>[3, 1, 0, 12, 11, 9, 10, 7, 4, 5, 6], 3=>[2, 4, 1, 0, 12, 11, 6, 9, 5, 8, 7], 4=>[5, 3, 6, 1, 0, 12, 8, 2, 9, 10], 5=>[4, 6, 7, 10, 8, 9, 0, 3, 2, 12, 11], 6=>[7, 5, 4, 8, 1, 0, 3, 10, 9, 11, 2], 7=>[6, 8, 5, 9, 10, 11, 2, 0, 12, 1, 3], 8=>[9, 7, 10, 6, 5, 1, 4, 12, 11, 3, 0], 9=>[8, 10, 11, 7, 2, 5, 3, 6, 4, 0, 1], 10=>[11, 9, 8, 5, 7, 2, 6, 1, 0, 4, 12], 11=>[10, 12, 9, 2, 3, 7, 1, 8, 6, 5], 12=>[0, 11, 2, 3, 4, 1, 8, 7, 5, 10]}

Gen: 12
Queue Before: [4, 2, 6, 3, 7, 11, 5, 1, 9, 8, 0, 12, 10]
Linked: [[4, 7], [5, 1], [2, 8], [11, 0], [6, 12], [3, 10]]
Queue After: [9]
Link History: {0=>[1, 12, 2, 3, 4, 6, 5, 7, 10, 9, 8, 11], 1=>[0, 2, 3, 4, 6, 8, 12, 11, 10, 7, 9, 5], 2=>[3, 1, 0, 12, 11, 9, 10, 7, 4, 5, 6, 8], 3=>[2, 4, 1, 0, 12, 11, 6, 9, 5, 8, 7, 10], 4=>[5, 3, 6, 1, 0, 12, 8, 2, 9, 10, 7], 5=>[4, 6, 7, 10, 8, 9, 0, 3, 2, 12, 11, 1], 6=>[7, 5, 4, 8, 1, 0, 3, 10, 9, 11, 2, 12], 7=>[6, 8, 5, 9, 10, 11, 2, 0, 12, 1, 3, 4], 8=>[9, 7, 10, 6, 5, 1, 4, 12, 11, 3, 0, 2], 9=>[8, 10, 11, 7, 2, 5, 3, 6, 4, 0, 1], 10=>[11, 9, 8, 5, 7, 2, 6, 1, 0, 4, 12, 3], 11=>[10, 12, 9, 2, 3, 7, 1, 8, 6, 5, 0], 12=>[0, 11, 2, 3, 4, 1, 8, 7, 5, 10, 6]}

Gen: 13
Queue Before: [9, 4, 7, 5, 1, 2, 8, 11, 0, 6, 12, 3, 10]
Linked: [[4, 11], [9, 12]]
Queue After: [7, 5, 1, 2, 8, 0, 6, 3, 10]
Link History: {0=>[1, 12, 2, 3, 4, 6, 5, 7, 10, 9, 8, 11], 1=>[0, 2, 3, 4, 6, 8, 12, 11, 10, 7, 9, 5], 2=>[3, 1, 0, 12, 11, 9, 10, 7, 4, 5, 6, 8], 3=>[2, 4, 1, 0, 12, 11, 6, 9, 5, 8, 7, 10], 4=>[5, 3, 6, 1, 0, 12, 8, 2, 9, 10, 7, 11], 5=>[4, 6, 7, 10, 8, 9, 0, 3, 2, 12, 11, 1], 6=>[7, 5, 4, 8, 1, 0, 3, 10, 9, 11, 2, 12], 7=>[6, 8, 5, 9, 10, 11, 2, 0, 12, 1, 3, 4], 8=>[9, 7, 10, 6, 5, 1, 4, 12, 11, 3, 0, 2], 9=>[8, 10, 11, 7, 2, 5, 3, 6, 4, 0, 1, 12], 10=>[11, 9, 8, 5, 7, 2, 6, 1, 0, 4, 12, 3], 11=>[10, 12, 9, 2, 3, 7, 1, 8, 6, 5, 0, 4], 12=>[0, 11, 2, 3, 4, 1, 8, 7, 5, 10, 6, 9]}
 

 

Notice that it takes 14 generations to go through them all (number of worlds + 1), and the last generation only has two portals open between #4-#11, and #9-#12, while the rest of the worlds are portal-less.  Depending on which is stricter requirements, you can keep it to 13 generations before reseting the link history just knowing that #4-#11 and #9-#12 will never have portals together.

Edited by alnite

Share this post


Link to post
Share on other sites

I thought that was clear enough with that, but I guess not...

 

World 1 and World 2 can only connect to each other, but can't connect to any other World during each point when portals open.

The link is bi-directional so World 1 can't connect to World 2 which connects to World 3.

In other words there are only 6 links possible during each open portal period.

 

There are 78 pairs in the cycle and 78 possible unique pairs... These should be divided into 13 sets of 6. (one of the Worlds aren't connected with each configuration and it's a different one with each of the 13 sets.) This all seems to indicate that there is only 1 possible way to do this.

 

Other than these thing I don't think there is any other restrictions.

 

---

Yes 1 World will not have a portal in every generation.

The world that does not get a portal shifts every generation... and because these are all happening at once the one that does not connect should only repeat when each of the other worlds have not connected... Not connecting can be treated as another world in that regard.

 

There is no "rule" for selecting. That's part of the problem. I'd like there to be an easy rule or a pattern, but I need each world to connect to every other world is the priority so if I can't find a pattern from those other rules i guess there is no rule.

 

So you're example doesn't work, because World 12 would not be the one left out twice in the same cycle.

----

 

Also, the fact that these links all have to be unique by it's very nature, it's easy to make a list for a generation of a few that works, but when you try to make it for all 13 I find it very hard.

Share this post


Link to post
Share on other sites

Consider it like this...

 

Here are all the possible pairs that can exist in cycle. If they are alone, they go nowhere...

 

---------------------------

[00]
[01, 00] [01]
[02, 00] [02, 01] [02]
[03, 00] [03, 01] [03, 02] [03]
[04, 00] [04, 01] [04, 02] [04, 03] [04]
[05, 00] [05, 01] [05, 02] [05, 03] [05, 04] [05]
[06, 00] [06, 01] [06, 02] [06, 03] [06, 04] [06, 05] [06]
[07, 00] [07, 01] [07, 02] [07, 03] [07, 04] [07, 05] [07, 06] [07]
[08, 00] [08, 01] [08, 02] [08, 03] [08, 04] [08, 05] [08, 06] [08, 07] [08]
[09, 00] [09, 01] [09, 02] [09, 03] [09, 04] [09, 05] [09, 06] [09, 07] [09, 08] [09]
[10, 00] [10, 01] [10, 02] [10, 03] [10, 04] [10, 05] [10, 06] [10, 07] [10, 08] [10, 09] [10]
[11, 00] [11, 01] [11, 02] [11, 03] [11, 04] [11, 05] [11, 06] [11, 07] [11, 08] [11, 09] [11, 10] [11]
[12, 00] [12, 01] [12, 02] [12, 03] [12, 04] [12, 05] [12, 06] [12, 07] [12, 08] [12, 09] [12, 10] [12, 11] [12]
---------------------
 
And then there is 
 
Gen 1
Nowhere Slot : 
Pair 1 Slot: 
Pair 2 Slot: 
Pair 3 Slot: 
Pair 4 Slot: 
Pair 5 Slot: 
Pair 6 Slot: 
 
Repeat that for 13 generations.
 
Each slot of the 13 generations cannot be duplicated in another slot.
Each Slot within the generation cannot have a repeat of a number so once [00] is used every pair with "00" in it cannot be used in that generation.
 
So once it's used you can just take it out of the list.
 
I'm sure there is a way to brute force it, but that seems like a lot of processing where there should be some way to sort quickly I'd think.
Edited by Durakken

Share this post


Link to post
Share on other sites

Just a recursive function?

class Connects:
    """Connects in one turn"""
    def __init__(self):
        self.ww = {}
        self.sw = None

    def __str__(self):
        return str(self.ww)

    def connect(self, orig, dest):
        if orig == dest:
            if self.sw is not None:
                return False
            self.sw = orig
            self.ww[orig] = orig
            return True
        else:
            if self.ww.get(dest) is not None:
                return False
            self.ww[orig] = dest
            self.ww[dest] = orig
            return True

    def unconnect(self, orig, dest):
        if orig == dest:
            self.sw = None
            del self.ww[orig]
        else:
            del self.ww[orig]
            del self.ww[dest]

    def is_connected(self, orig):
        return orig in self.ww


history = [set() for _ in range(13)]

def connect(history, ch, connects, w):
    """Connect w in connects for this turn, not violating the history"""

    if w == 13:
        newh = [s.copy() for s in history]
        for k, v in connects.ww.items():
            newh[k].add(v)
            newh[v].add(k)

        ch.append(connects)

        if len(newh[0]) == 13:
            for c in ch:
                print(c)
            return True

        return connect(newh, ch, Connects(), 0)

    if connects.is_connected(w):
        return connect(history, ch, connects, w+1)

    for ow in range(13):
        if ow in history[w]: continue
        if connects.connect(w, ow):
            ret = connect(history, ch, connects, w+1)
            if ret: return ret
            connects.unconnect(w, ow)
    return False

connect(history, [], Connects(), 0)

Dumps in less than a second computation time, so either there is loads of room (I quit on the first solution), or the problem is so constrained it walks right to a solution.

{0: 0, 1: 2, 2: 1, 3: 4, 4: 3, 5: 6, 6: 5, 7: 8, 8: 7, 9: 10, 10: 9, 11: 12, 12: 11}
{0: 1, 1: 0, 2: 2, 3: 5, 4: 6, 5: 3, 6: 4, 7: 9, 8: 11, 9: 7, 10: 12, 11: 8, 12: 10}
{0: 2, 1: 1, 2: 0, 3: 6, 4: 5, 5: 4, 6: 3, 7: 10, 8: 12, 9: 11, 10: 7, 11: 9, 12: 8}
{0: 3, 1: 4, 2: 5, 3: 0, 4: 1, 5: 2, 6: 6, 7: 11, 8: 10, 9: 12, 10: 8, 11: 7, 12: 9}
{0: 4, 1: 3, 2: 6, 3: 1, 4: 0, 5: 5, 6: 2, 7: 12, 8: 9, 9: 8, 10: 11, 11: 10, 12: 7}
{0: 5, 1: 7, 2: 8, 3: 9, 4: 10, 5: 0, 6: 11, 7: 1, 8: 2, 9: 3, 10: 4, 11: 6, 12: 12}
{0: 6, 1: 8, 2: 7, 3: 10, 4: 9, 5: 12, 6: 0, 7: 2, 8: 1, 9: 4, 10: 3, 11: 11, 12: 5}
{0: 7, 1: 5, 2: 9, 3: 8, 4: 11, 5: 1, 6: 12, 7: 0, 8: 3, 9: 2, 10: 10, 11: 4, 12: 6}
{0: 8, 1: 6, 2: 10, 3: 7, 4: 12, 5: 11, 6: 1, 7: 3, 8: 0, 9: 9, 10: 2, 11: 5, 12: 4}
{0: 9, 1: 10, 2: 11, 3: 12, 4: 4, 5: 7, 6: 8, 7: 5, 8: 6, 9: 0, 10: 1, 11: 2, 12: 3}
{0: 10, 1: 11, 2: 12, 3: 3, 4: 7, 5: 8, 6: 9, 7: 4, 8: 5, 9: 6, 10: 0, 11: 1, 12: 2}
{0: 11, 1: 12, 2: 3, 3: 2, 4: 8, 5: 9, 6: 10, 7: 7, 8: 4, 9: 5, 10: 6, 11: 0, 12: 1}
{0: 12, 1: 9, 2: 4, 3: 11, 4: 2, 5: 10, 6: 7, 7: 6, 8: 8, 9: 1, 10: 5, 11: 3, 12: 0}

Above is a "from:to"  pair list, for each turn, where one world connects to itself, if I made no error in the implementation

Share this post


Link to post
Share on other sites

Thank's Alberth. I'm checking it long form... It looks right so far to me.

 

edit: Finish checking... It is 100% perfect ^.^. Again. Thanks

Edited by Durakken

Share this post


Link to post
Share on other sites

I am late to the thread and I didn't read the whole thing, but I think I know a very easy way to do it. You basically have 14 volleyball teams (including "nowhere") and you want to organize a league, so over 13 rounds every team plays every other team. The traditional way to do it is having 7 courts and having team 1 fixed and everyone else rotate, like this:

 

Round 1:
 1   2   3   4   5   6   7
14  13  12  11  10   9   8
 
Round 2:
 1  14   2   3   4   5   6 
13  12  11  10   9   8   7
 
Round 3:
 1  13  14   2   3   4   5
12  11  10   9   8   7   6
 
...

 

Does that make sense?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!