Finding permutations of lists using sublists

Question

I was looking at this website about recursion. Where I found this example of using recursion to find the permutations of a list of people:

def fill_seats(people):
   # Return a list of ways to fill len(people) seats with the people
   # named in the sequence people.
   if len(people) == 0:
       return []
   else:
      possible = []
      for i in range(len(people)):
         this_person = people[i]
         everyone_else = people[:i] + people[i+1:]
         for seating_arrangement in fill_seats(everyone_else):
            possible = possible + [[this_person] + seating_arrangement]
      return possible

our_class = ["Biella", "Gwen", "Katie", "Seth", "Will"]

for arrangement in fill_seats(our_class):
    print arrangement

print len(fill_seats(our_class)), "total possible arrangements."

However it keeps return 0 and I have no idea why, any ideas? And how exactly are the substrings working in this case? Don't they just splice the individual items in the list? What purpose would that have?

score 2 · Accepted Answer · answered Feb 25 '14 at 05:24

2

All you need to change is

if len(people) == 1:
    return [people]

Because, when people is [], it returns an empty list. So, if people has only one element, the fill_seats(everyone_else) will return [], so possible will also return []. The same is returned through the chain and finally returned back.

With that change, the output becomes

['Biella', 'Gwen', 'Katie', 'Seth', 'Will']
['Biella', 'Gwen', 'Katie', 'Will', 'Seth']
['Biella', 'Gwen', 'Seth', 'Katie', 'Will']
...
...
...
['Will', 'Seth', 'Gwen', 'Katie', 'Biella']
['Will', 'Seth', 'Katie', 'Biella', 'Gwen']
['Will', 'Seth', 'Katie', 'Gwen', 'Biella']
120 total possible arrangements.

answered Feb 25 '14 at 05:24

thefourtheye

233,700
52
457
497

wouldn't that return a list of a list? – Russia Must Remove Putin Feb 25 '14 at 05:25
@AaronHall It will return a list of string, but that list of string is concatenated in `[[this_person] + seating_arrangement]`. So, that should be fine. – thefourtheye Feb 25 '14 at 05:27
if people is a string, it's len would likely be > 1, right? – Russia Must Remove Putin Feb 25 '14 at 05:28
But `people` wasn't an empty list, why was it treating it as such? – Amon Feb 25 '14 at 05:39

jayelm · Answer 2 · 2014-02-25T05:38:08.323

1

To answer your question about the slicing, these aren't substrings, they're sublists. For example, if people is the following list:

people = ['Adam', 'Betsy', 'Charlie', 'David']

We begin iterating through every index in people. So our first iteration would assign

>>> this_person = people[0]
>>> this_person
'Adam'

And then everyone_else would be:

>>> people[:0]
[]
>>> people[1:]
['Betsy', 'Charlie', 'David']
>>> everyone_else = people[:0] + people[1:]
>>> everyone_else
['Betsy', 'Charlie', 'David']

Basically, you're reconstructing the list leaving out the current index i, then recursing with the smaller list.

When i = 1, it looks like this:

>>> this_person = people[1]
'Betsy'
>>> people[:1]
['Adam']
>>> people[2:]
['Charlie', 'David']
>>> everyone_else = people[:1] + people[2:]
>>> everyone_else
['Adam', 'Charlie', 'David']

edited Feb 25 '14 at 05:38

answered Feb 25 '14 at 05:30

jayelm

7,236
5
43
61

Oh okay, so the `[:]` sytax is just a slicer? I thought it was only for strings my mistake. Thanks – Amon Feb 25 '14 at 05:33
Also, what's the point of having `people[:0]`? Why not just have `people[1:]`? Adding them together seems redundant – Amon Feb 25 '14 at 05:35
1

@Amon that's the special case when `people[:0]` returns an empty list. See my edit – jayelm Feb 25 '14 at 05:38

Finding permutations of lists using sublists

2 Answers2