StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here's a quick program I threw together to solve this. It's probably not the most efficient way to go about this, but it gets the job done.</p> <pre><code>l = [(1,2),(2,3),(3,4),(4,5)] # replace with whatever your full list is import itertools for perm in itertools.permutations(l,len(l) / 2): pair_list = [] for pair in perm: if pair[0] in itertools.chain(*(i for i in pair_list)) \ or pair[1] in itertools.chain(*(i for i in pair_list)): break pair_list.append(pair) if len(pair_list) == len(l) / 2: unused = [] for n in itertools.chain(*(i for i in l)): if n not in itertools.chain(*(i for i in pair_list)) and n not in unused: unused.append(n) print pair_list,'unused:',unused </code></pre> <p>Also, are you sure you want to identify all the permutations? To get your exact output, I would need to replace <code>itertools.permutations</code> with <code>itertools.combinations</code>.</p> <p>Here is the output I get using <code>itertools.permutations</code>:</p> <pre><code>[(1, 2), (3, 4)] unused: [5] [(1, 2), (4, 5)] unused: [3] [(2, 3), (4, 5)] unused: [1] [(3, 4), (1, 2)] unused: [5] [(4, 5), (1, 2)] unused: [3] [(4, 5), (2, 3)] unused: [1] </code></pre> <p>Whereas what I get using <code>itertools.combinations</code>:</p> <pre><code>[(1, 2), (3, 4)] unused: [5] [(1, 2), (4, 5)] unused: [3] [(2, 3), (4, 5)] unused: [1] </code></pre> <p><strong>Edit:</strong> Ok, it got a bit tougher with this new revision. What I do now is find all the subgroups within the larger list where the pairs are all adjacent to one another. I find the combinations for each of the subgroups, then put them all back together with an <code>itertools.product</code> at the end. Also, in my test case, I added an extra pair (8,9) to the end to make sure that everything worked for multiple groups. Here's the code:</p> <pre><code>l = [(1,2),(2,3),(3,4),(4,5),(7,8),(8,9)] import itertools,math ## Create sublists for each set of adjacent pairs l.sort(lambda x,y:cmp(x[0],y[0])) newl = [] subl = [] for i in range(len(l)): if subl == []: subl.append(l[i]) else: if l[i][0] == subl[-1][1]: subl.append(l[i]) else: newl.append(subl) subl = [l[i]] newl.append(subl) pair_lists = [] ## Find all combinations for each sublist for subl in newl: cur_pair_list = [] for perm in itertools.combinations(subl,int(math.ceil(len(subl) / 2.0))): pair_list = [] for pair in perm: if pair[0] in itertools.chain(*pair_list) \ or pair[1] in itertools.chain(*pair_list): break pair_list.append(pair) if len(pair_list) == int(math.ceil(len(subl) / 2.0)): cur_pair_list.append(pair_list) pair_lists.append(cur_pair_list) ## Combine combinations for each sublist and determine unused for each combination final_list = list(list(itertools.chain(*i)) for i in itertools.product(*pair_lists)) for subl in final_list: unused = [] for n in itertools.chain(*l): if n not in itertools.chain(*subl) and n not in unused: unused.append(n) print subl,'unused:',unused </code></pre> <p>And here's the output:</p> <pre><code>[(1, 2), (3, 4), (7, 8)] unused: [5, 9] [(1, 2), (3, 4), (8, 9)] unused: [5, 7] [(1, 2), (4, 5), (7, 8)] unused: [3, 9] [(1, 2), (4, 5), (8, 9)] unused: [3, 7] [(2, 3), (4, 5), (7, 8)] unused: [1, 9] [(2, 3), (4, 5), (8, 9)] unused: [1, 7] </code></pre> <p><strong>Edit #2:</strong> So here, then only new thing I had to do was change the way that the list was sorted. All the code below the comment <code>## Find all combinations for each sublist</code> can stay the same. </p> <p>Here's the new code that goes above that comment:</p> <pre><code>l = [(427, 3434), (614, 2445), (840, 614), (910, 3939), (1065, 4314), (1347, 2616), (2445, 427), (2616, 3901), (2749, 1065), (3403, 910), (3434, 1347), (3659, 1411), (3901, 3684), (3939, 2638), (4203, 3403), (4314, 840)] import itertools,math def sort(l): l = list(l) newl = [] subl = [] i = l[0] while len(l) > 0: subl.append(i) l.remove(i) k = None for j in l: if j[0] == i[1]: k = j break if k: i = k else: newl.append(subl) subl = [] if len(l) > 0: i = l[0] i = 0 while i < len(newl): j = 0 while j < len(newl): if newl[j][-1][1] == newl[i][0][0]: for k in newl[j][::-1]: newl[i].insert(0,k) newl.pop(j) continue j += 1 i += 1 return newl pair_lists = [] newl = sort(l) </code></pre> <p>Here's the output I get when I run this on your new list:</p> <pre><code>[(2749, 1065), (4314, 840), (614, 2445), (427, 3434), (1347, 2616), (3901, 3684), (4203, 3403), (910, 3939), (3659, 1411)] unused: [2638] [(2749, 1065), (4314, 840), (614, 2445), (427, 3434), (1347, 2616), (3901, 3684), (4203, 3403), (3939, 2638), (3659, 1411)] unused: [910] [(2749, 1065), (4314, 840), (614, 2445), (427, 3434), (1347, 2616), (3901, 3684), (3403, 910), (3939, 2638), (3659, 1411)] unused: [4203] </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload