fork download
copy 
  1. # Generate successive k-length permutations. (4.01)
  2. # @note Rewrite of the code that appears at
  3. # docs.python.org/3/library/itertools.html#itertools.permutations
  4. # (eliminates indirect indexing; derive from direct if needed).
  5. # @see 3UOMj3, vSELdo, cTaz9y
  6.  
  7. def permutations(iterable, k=None):
  8.     items = list(iterable)
  9.     n = len(items)
  10.     if k is None:
  11.         k = n
  12.     elif k > n:
  13.         return
  14.     elif k < 0:
  15.         raise ValueError('k must be non-negative')
  16.     cycle = list(range(k))
  17.     yield tuple(items[:k])
  18.     i = k-1
  19.     while i >= 0:
  20.         j = cycle[i] + 1
  21.         if j < n:
  22.             cycle[i] = j
  23.             items[i], items[j] = items[j], items[i]
  24.             yield tuple(items[:k])
  25.             i = k-1
  26.         else:
  27.             cycle[i] = i
  28.             items.append(items.pop(i))
  29.             i = i-1
  30.  
  31. def permutations_indirect(iterable, k=None):
  32.     pool = tuple(iterable)
  33.     for index in permutations(range(len(pool)), k):
  34.         yield tuple(pool[i] for i in index)
  35.  
  36. # Test.
  37.  
  38. import itertools
  39. import time
  40.  
  41. n = 3
  42. a = list(range(n))
  43. for k in range(2+len(a)):
  44.     print(list(permutations(a, k)))
  45.     print(list(itertools.permutations(a, k)))
  46.  
  47. def test(f, a):
  48.     for k in itertools.chain([None], range(2+len(a))):
  49.         m = sum(1 for _ in f(a, k))
  50.         n = sum(1 for _ in itertools.permutations(a, k))
  51.         assert m == n
  52.         for x, y in zip(f(a, k), itertools.permutations(a, k)):
  53.             assert x == y
  54.     t = time.process_time()
  55.     for _ in f(a):
  56.         pass
  57.     t = time.process_time() - t
  58.     print('Elapsed: {:.6f}s'.format(t))
  59.  
  60. n = 8
  61. a = list(range(n))
  62. test(permutations, a)
  63. test(permutations_indirect, a)
  64. test(itertools.permutations, a)
Success #stdin #stdout 0.92s 14224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[()]
[()]
[(0,), (1,), (2,)]
[(0,), (1,), (2,)]
[(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)]
[(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)]
[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]
[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]
[]
[]
Elapsed: 0.017115s
Elapsed: 0.045164s
Elapsed: 0.002101s
https://ideone.com/Z7vqGh
language:
Python 3 (python  3.12)
created:
19 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!