I'm going to call my procedure sublists.
We saw before when I drew it out that we wanted 2 arguments:
the big list of people that I'm going to invite to my party
and the people that I've selected so far.
As we make recursive calls to sublists,
the big list of people I've yet to invite will shrink,
and then selected so far--the people who have showed up to my party--
may or may not grow. They may show up or not.
So this is a recursive procedure, and every recursive procedure needs a base case
or a stopping condition.
If there's no one left to invite, then I'll just print out the people we've selected so far.
Remember when I drew the tree at the bottom there were 8 answers?
When I get down to the end, I want to print out each of those 8 answers.
If the big list is not empty, then it has at least 1 element--
the current element, I'll call it--and then here I've just put the rest of the list,
which is everything after the current element.
May be empty; may have more things.
In this recursive procedure, we're going to call ourselves 2 times.
There's 1 case where the current person responds to our dinner invitation
and ends up being one of the people we select,
and there's another case where they do not. And that's actually it.
Here's a test program.
My dinner guests are Lucretia Mott, Elizabeth Cady Stanton, and Susan B. Anthony,
and I'm going to call sublists, and the big list of people is dinner guests,
and the people I've chosen so far is nothing.
Let's see if this works.
And in fact, we got just the answer we wanted.
There's 1 world where everyone shows up,
1 world where no one shows up, 3 worlds with just 1 person,
and 3 worlds with 2 people each, for a total of 8.
このプロシージャをsublistsと呼びます
この2つの引数は前にも見ましたね
私が招待したい人のリストbig_listと
私が選んだ人のリストselected_so_farです
sublistを再帰的に呼び出すにつれて
大きな招待リストは小さくなっていき
選ばれてパーティーに来た人のリストは
大きくなる可能性もあるしないともいえます
これが再帰プロシージャです
すべてのプロシージャにはベースケースとなる場合
つまり停止条件が必要です
招待する人が誰もいなくなったら
これまでに選んだ人たちを出力します
木を書いた時
8つの答えがあったのを思い出してください
下までたどりついた時に
その8つの答えを出力します
もしbig_listが空でなければ
最低1つの要素があります
これをcurrent_elementと呼ぶことにします
ここにはrest_of_big_listを置きます
current_elementのあとに来るものすべてです
ここは空かもしれませんし
要素があるかもしれません
この再帰プロシージャでは
自分自身を2回呼び出します
current_elementの人が夕食の招待に
返事をする場合が1つあります
そして選んだ人の1人になる場合と
ならない場合があります
これはならない場合です
これはテストプログラムです
招待した友人はルクレチア、エリザベス、
スーザンです
これをsublistsに渡して呼ぶことにします
大きい方のリストは招待者dinner_guestです
今のところ私が選んだ人はいません
これがうまくいくか見てみましょう
実は求めていた答えがここにあります
全員が来る場合が1つ
誰も来ない場合が1つ、1人が来る場合が3つ、
2人が来る場合が3つの合計8つです
Vou chamar miha função de sublists.
vimos anteriormente qeu ela tem 2 argumentos:
a lista de pessoas que eu vou convidar para minha festa,
e as pessoas que já selecionei anteriormente.
À medida que chamamos subslists recursivamente,
a lista de pessoas a convidar diminui,
e as que já selecionei -- as pessoas que já apareceram para a festa --
pode ou não crescer. Elas podem vir ou não.
Então, isso é uma função recursiva, e toda funçào recursiva precisa de um caso base,
ou uma condição de parada.
Se não existe mais ninguém para ser convidado, simplesmente imprimimos as pessoas selecionadas até então.
Lembra-se que na árvore que desenhei aqui embaixo haviam 8 respostas?
Quando eu chego aqui, quero imprimir cada uma dessas 8 respostas.
Se a lista for não vazia, então ela tem pelo menos 1 elemento --
o elemento corrente. Eu chamo este elemento e aqui tenho o restante da lista,
que é tudo que vem depois do elemento corrente.
Pode ser vazia, ou pode ter mais elementos.
Nesta função recursiva temos 2 chamadas a ela própria:
uma no caso em que a pessoa corrente aceita nosso convite para jantar,
e é incluída entre as pessoas que selecionamos,
e a outra no caso em que ela não aceita. E é isso!
Aqui está o programa para teste.
Meus convidados são Lucretia Mott, Elizabeth Cady Satanton e Susan B. Antony,
e eu vou chamar sublists, com minha grande lista de convidados,
e a lista de pessoas selecionadas até agora, que é vazai.
Vamos ver se funciona.
De fato, obtemos a resposta que queríamos.
Existe 1 mundo no qual todo mundo aparece,
1 mundo em que não há nunguém, 3 mundos com apenas 1 pessoa,
e 3 mundos com duas pessoas cada -- um total de 8.