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?

Answer 1

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.

• Aaron Hall: wouldn't that return a list of a list?
• thefourtheye: @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.
• Aaron Hall: if people is a string, it's len would likely be > 1, right?
• Amon: But people wasn't an empty list, why was it treating it as such?

Answer 2

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']

• Amon: Oh okay, so the [:] sytax is just a slicer? I thought it was only for strings my mistake. Thanks
• Amon: Also, what's the point of having people[:0]? Why not just have people[1:]? Adding them together seems redundant
• jayelm: @Amon that's the special case when people[:0] returns an empty list. See my edit