Edit: This is not a exact duplicate of How to get all possible combinations of a list’s elements?
This topic is about finding unique combinations while the other topic is about finding ALL combinations.
If I have a python list:
L = [1,2,3,4]
what's the best way to get all the possible unique combinations of 3 elements from the list like below:
["1,2,3", "1,2,4", "2,3,4", "3,4,1"]
The order of the elements in the combinations doesn't matter. For example, "1,2,3"
and "3,2,1"
will be considered the same combination.
I can probably write a few loops to do this but I think there might be a one-liner which can do the same.
I tried to get the all unique pair combinations from a list.
Here is what I have done so far,
import itertools
# Unique Combination Pairs for list of elements
def uniqueCombinations[list_elements]:
l = list[itertools.combinations[list_elements, 2]]
s = set[l]
# print['actual', len[l], l]
return list[s]
Test Case
sample = ["apple", "orange", "banana", "grapes", "mango"]
uniqueCombinations[sample]
Output
[['apple', 'banana'],
['orange', 'mango'],
['orange', 'grapes'],
['apple', 'grapes'],
['orange', 'banana'],
['apple', 'mango'],
['grapes', 'mango'],
['apple', 'orange'],
['banana', 'mango'],
['banana', 'grapes']]
The input will be unique strings of list. Assume that duplicate elements will not be passed.
Is there a better / more elegant / more accurate way to do this??
Generate list of unique pairs [a, b] from N elements ensuring all elements participate in a and b.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
import sys, random | |
fout = open['pairs.txt', 'w'] | |
# total number of people participating | |
total_people = int[sys.argv[1]] | |
a, b = [], [] | |
for i in xrange[1, total_people+1]: | |
a.append[i] | |
while True: | |
r = random.randint[1, total_people] | |
if r not in b and r != i: | |
b.append[r] | |
break | |
for i, j in zip[a, b]: | |
fout.write[str[i]+" "+str[j]+"\n"] | |
fout.close[] |
Given a list. The task is to write a Python program to get all pairwise combinations from the list.
Finding all Pairs [No uniqueness]
Example:
Input: [1,”Mallika”,2,”Yash”]
Output: [[1, ‘Mallika’], [1, 2], [1, ‘Yash’], [‘Mallika’, 1], [‘Mallika’, 2], [‘Mallika’, ‘Yash’], [2, 1], [2, ‘Mallika’], [2, ‘Yash’], [‘Yash’, 1], [‘Yash’, ‘Mallika’], [‘Yash’, 2]]
Method 1: Using simple loops
We can access all combinations of the list using two loops to iterate over list indexes. If both the index counters are on the same index value, we skip it, else we print the element at index i followed by the element at index j in order.
The time complexity of this method is O[n2] since we require two loops to iterate over lists.
Python3
lst
=
[
1
,
"Mallika"
,
2
,
"Yash"
]
output
=
[]
for
i
in
range
[
0
,
len
[lst]]:
for
j
in
range
[
0
,
len
[lst]]:
if
[i!
=
j]:
output.append[[lst[i],lst[j]]]
print
[output]
Output:
[[1, ‘Mallika’], [1, 2], [1, ‘Yash’], [‘Mallika’, 1], [‘Mallika’, 2], [‘Mallika’, ‘Yash’], [2, 1], [2, ‘Mallika’], [2, ‘Yash’], [‘Yash’, 1], [‘Yash’, ‘Mallika’], [‘Yash’, 2]]
Method 2: Using itertools
Python provides support of itertools standard library which is used to create iterators for efficient looping. The library provides support for various kinds of iterations, in groups, sorted order, etc. The permutations[] functions of this library are used to get through all possible orderings of the list of elements, without any repetitions. The permutations[] functions have the following syntax:
itertools.permutations[lst,r]
Where r depicts the r-length tuples, that is, 2 depicts a pair,3 depicts a triplet. The first argument is the specified list.
The function returns the list of groups of elements returned after forming the permutations. The output contains n x [n-1] number of elements, where n is the size of the list since each element is subsequently is multiplied with all others. The time required to compute permutations is roughly exponential in the order of the size of the list.
Python3
import
itertools
lst
=
[
1
,
"Mallika"
,
2
,
"Yash"
]
pair_order_list
=
itertools.permutations[lst,
2
]
print
[
list
[pair_order_list]]
Output:
[[1, ‘Mallika’], [1, 2], [1, ‘Yash’], [‘Mallika’, 1], [‘Mallika’, 2], [‘Mallika’, ‘Yash’], [2, 1], [2, ‘Mallika’], [2, ‘Yash’], [‘Yash’, 1], [‘Yash’, ‘Mallika’], [‘Yash’, 2]]
Note:
- The pairs are printed in the order of the sequence of arrival of elements in the list.
- In the case of all same elements, the method still continues to form pairs and return them, even if they are duplicates.
Python3
import
itertools
lst
=
[
2
,
2
,
2
]
ordered_list
=
itertools.permutations[lst,
2
]
for
i
in
ordered_list:
print
[i]
Output :
[2, 2] [2, 2] [2, 2] [2, 2] [2, 2] [2, 2]
Finding all Unique Pairs [Uniqueness]
However, the permutations’ method doesn’t distinguish between [a, b] and [b, a] pairs and returns them both. The itertools library also supports a combinations[] method that prints either of the [a, b] or [b, a] pairs and not both. The output number of elements is equivalent to [n-1]! where n is the length of the list. The time required to compute combinations is roughly polynomial.
Example:
Input: [1,”Mallika”,2,”Yash”]
Output: [[1, ‘Mallika’], [1, 2], [1, ‘Yash’], [‘Mallika’, 2], [‘Mallika’, ‘Yash’], [2, ‘Yash’]]
Python3
import
itertools
3
to integers
and
strings
lst
=
[
1
,
"Mallika"
,
2
,
"Yash"
]
pair_order_list
=
itertools.combinations[lst,
2
]
print
[
list
[pair_order_list]]
Output:
[[1, ‘Mallika’], [1, 2], [1, ‘Yash’], [‘Mallika’, 2], [‘Mallika’, ‘Yash’], [2, ‘Yash’]]