ATLAS Offline Software
combo.py
Go to the documentation of this file.
1 # Copyright (C) 2002-2020 CERN for the benefit of the ATLAS collaboration
2 
3 #
4 # $Id: combo.py,v 1.3 2005-05-12 16:36:59 ssnyder Exp $
5 # File: combo.py
6 # Created: sss, Mar 2005, from http://aspn.activestate.com/.
7 # Purpose: Generators for combinations and permutations.
8 #
9 
10 
11 """Generators for combinations and permutations.
12 
13 This module contains functions for
14 generating all combinations and permutations from a list of
15 items. These functions return generators, so you may iterate
16 over them or retrieve successive values with
17 next(). Given a sequence items,
18 you can iterate over the list of unique pairwise combinations with
19 
20  for (i1, i2) in combo.xuniqueCombinations (items, 2):
21 
22 The functions contained in this module are:
23 
24  combinations(items,n)
25  Yields all unique subsequences of length n from items.
26 
27  all_combinations(items,n)
28  Similar, but differences in ordering are considered significant.
29  For example, all_combinations([1,2,3],2) will yield both [1,2] and [2,1].
30 
31  permutations(items)
32  Yields all permutations of items.
33  Equivalent to all_combinations(items,len(items)).
34 
35  selections(items,n)
36  Returns all possible ways of picking n items from
37  items, where any given item may be picked multiple times.
38 """
39 
40 from builtins import range
41 __version__ = "1.0"
42 
43 """combo.py
44 Generators for calculating a) the permutations of a sequence and
45 b) the combinations and selections of a number of elements from a
46 sequence. Uses Python 2.2 generators.
47 
48 Similar solutions found also in comp.lang.python
49 
50 Keywords: generator, combination, permutation, selection
51 
52 See also: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/105962
53 See also: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66463
54 See also: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66465
55 """
56 
57 def all_combinations(items, n):
58  """Return all subsequences of length n from items.
59 Differences in ordering are considered significant.
60 For example, all_combinations([1,2,3],2) will yield both [1,2] and [2,1].
61 
62 >>> for c in all_combinations(['l','o','v','e'],2):
63 ... print (''.join(c))
64 lo
65 lv
66 le
67 ol
68 ov
69 oe
70 vl
71 vo
72 ve
73 el
74 eo
75 ev
76 """
77  if n==0:
78  yield []
79  else:
80  for i in range(len(items)):
81  for cc in all_combinations(items[:i]+items[i+1:],n-1):
82  yield [items[i]]+cc
83 
84 def combinations(items, n):
85  """Yields all unique subsequences of length n from items.
86 
87 >>> for uc in combinations(['l','o','v','e'],2):
88 ... print (''.join(uc))
89 lo
90 lv
91 le
92 ov
93 oe
94 ve
95 """
96  if n==0:
97  yield []
98  else:
99  for i in range(len(items)):
100  for cc in combinations(items[i+1:],n-1):
101  yield [items[i]]+cc
102 
103 def selections(items, n):
104  """Returns all possible ways of picking n items from
105 items, where any given item may be picked multiple times.
106 
107 >>> for s in selections(['l','o','v','e'],2):
108 ... print (''.join(s))
109 ll
110 lo
111 lv
112 le
113 ol
114 oo
115 ov
116 oe
117 vl
118 vo
119 vv
120 ve
121 el
122 eo
123 ev
124 ee
125 """
126  if n==0:
127  yield []
128  else:
129  for i in range(len(items)):
130  for ss in selections(items, n-1):
131  yield [items[i]]+ss
132 
133 def permutations(items):
134  """ Yields all permutations of items.
135 Equivalent to all_combinations(items,len(items)).
136 
137 >>> for p in permutations(['l','o','v','e']):
138 ... print (''.join(p))
139 love
140 loev
141 lvoe
142 lveo
143 leov
144 levo
145 olve
146 olev
147 ovle
148 ovel
149 oelv
150 oevl
151 vloe
152 vleo
153 vole
154 voel
155 velo
156 veol
157 elov
158 elvo
159 eolv
160 eovl
161 evlo
162 evol
163 """
164  return all_combinations(items, len(items))
165 
166 
167 __test__ = {}
168 __test__['tests'] = """
169 >>> # Permutations of 'love'
170 >>> print (list(map(''.join, list(permutations('done')))))
171 ['done', 'doen', 'dnoe', 'dneo', 'deon', 'deno', 'odne', 'oden', 'onde', 'oned', 'oedn', 'oend', 'ndoe', 'ndeo', 'node', 'noed', 'nedo', 'neod', 'edon', 'edno', 'eodn', 'eond', 'endo', 'enod']
172 """
173 
174 
175 if __name__ == "__main__":
176  print ('PyAnalysisUtils/combo.py test')
177  import doctest
178  doctest.testmod()
python.combo.all_combinations
def all_combinations(items, n)
Definition: combo.py:57
plotBeamSpotVxVal.range
range
Definition: plotBeamSpotVxVal.py:194
python.combo.permutations
def permutations(items)
Definition: combo.py:133
python.combo.selections
def selections(items, n)
Definition: combo.py:103
python.combo.combinations
def combinations(items, n)
Definition: combo.py:84