back to listing index

How to generate all permutations of a list in Python

[web search]
Original source (stackoverflow.com)
Tags: python algorithms interview-questions permutations
Clipped on: 2017-04-24

Image (Asset 1/34) alt=

If you're using an older Python (<2.6) for some reason or are just curious to know how it works, here's one nice approach, taken from http://code.activestate.com/recipes/252178/:

def all_perms(elements):
    if len(elements) <=1:
        yield elements
    else:
        for perm in all_perms(elements[1:]):
            for i in range(len(elements)):
                # nb elements[0:1] works in both string and list contexts
                yield perm[:i] + elements[0:1] + perm[i:]

A couple of alternative approaches are listed in the documentation of itertools.permutations. Here's one:

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

And another, based on itertools.product:

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)

Hot Network Questions

Technology Life / Arts Culture / Recreation Science Other
  1. Stack Overflow
  2. Server Fault
  3. Super User
  4. Web Applications
  5. Ask Ubuntu
  6. Webmasters
  7. Game Development
  8. TeX - LaTeX
  9. Software Engineering
  10. Unix & Linux
  11. Ask Different (Apple)
  12. WordPress Development
  1. Geographic Information Systems
  2. Electrical Engineering
  3. Android Enthusiasts
  4. Information Security
  5. Database Administrators
  6. Drupal Answers
  7. SharePoint
  8. User Experience
  9. Mathematica
  10. Salesforce
  11. ExpressionEngine® Answers
  12. Cryptography
  1. Code Review
  2. Magento
  3. Signal Processing
  4. Raspberry Pi
  5. Programming Puzzles & Code Golf
  6. more (7)
  1. Photography
  2. Science Fiction & Fantasy
  3. Graphic Design
  4. Movies & TV
  5. Music: Practice & Theory
  6. Seasoned Advice (cooking)
  7. Home Improvement
  8. Personal Finance & Money
  9. Academia
  10. more (8)
  1. English Language & Usage
  2. Skeptics
  3. Mi Yodeya (Judaism)
  4. Travel
  5. Christianity
  6. English Language Learners
  7. Japanese Language
  8. Arqade (gaming)
  9. Bicycles
  10. Role-playing Games
  11. Anime & Manga
  12. Motor Vehicle Maintenance & Repair
  13. more (17)
  1. MathOverflow
  2. Mathematics
  3. Cross Validated (stats)
  4. Theoretical Computer Science
  5. Physics
  6. Chemistry
  7. Biology
  8. Computer Science
  9. Philosophy
  10. more (3)
  1. Meta Stack Exchange
  2. Stack Apps
  3. Area 51
  4. Stack Overflow Talent
site design / logo © 2017 Stack Exchange Inc; user contributions licensed under cc by-sa 3.0 with attribution required
rev 2017.4.24.25749