Pythonのリスト：その要素の取りうる値が複数の場合のすべての組み合わせに対応するリストの生成方法

Question

前提・実現したいこと

下記のようなリストを自動的に生成するpythonプログラムを書きたいと思っています。

slist = [a0, a1, a2, a3, a4, - - - , an-1]

各要素aiの取りうる数値
a0 = 0
a1 = -1, 0, 1
a2 = (a1-1), a1, (a1+1)
a3 = (a2-1), a2, (a2+1)

---

an-1 = (an-2-1), an-2, (an-2+1)

リストの取りうる場合の数は、3**(n-1)個となると思います。
それらを、slist[i] の形で取得したいと思うのですが、どうすればよいでしょうか？

該当のソースコード

試したこと

考えましたが、どうしても思いつきませんでした。

補足情報（FW/ツールのバージョンなど）

python3.7を使っています。

補足情報（取得したいリストの事例）

2要素のリストの場合（n=2）
（3通り）
[0, -1]
[0, 0]
[0, -1]

3要素の場合（n=3）
（9通り）
[0, -1, -2]
[0, -1, -1]
[0, -1, 0]
[0, 0, -1]
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[0, 1, 2]

4要素の場合（n=4）
（3*(n-1）=27通りになります）
[0, -1, -2, -3]
[0, -1, -2, -2]
[0, -1, -2, -1]
[0, -1, -1, -2]
[0, -1, -1, -1]
[0, -1, -1, 0]
[0, -1, 0, -1]
[0, -1, 0, 0]
[0, -1, 0, 1]
[0, 0, -1, -2]
[0, 0, -1, -1]
[0, 0, -1, 0]
[0, 0, 0, -1]
[0, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 1, 0]
[0, 0, 1, 1]
[0, 0, 1, 2]
[0, 1, 0, -1]
[0, 1, 0, 0]
[0, 1, 0, 1]
[0, 1, 1, 0]
[0, 1, 1, 1]
[0, 1, 1, 2]
[0, 1, 2, 1]
[0, 1, 2, 2]
[0, 1, 2, 3]
以上です

Comments

[quickquip]

具体的な例、例えば元になる列が[3, 7, 10] の時ほしい結果はどうなるのか、とかn=3が4の時の結果などを完全に書くと伝わりやすいと思います。
今のところnの意味が伝わりません…

[quickquip]

slistが入力なのか、欲しいものなのかも読み取れませんでした。

[yoshikazu.egawa]

説明不足で申し訳ありません。slistが欲しいものです。
2要素のリストの場合（n=2）
（3通り）
[0, -1]
[0, 0]
[0, -1]
3要素の場合（n=3）
（9通り）
[0, -1, -2]
[0, -1, -1]
[0, -1, 0]
[0, 0, -1]
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[0, 1, 2]

[yoshikazu.egawa]

４要素の場合（n=4）
（３*(n-1）=27通りになります）
[0, -1, -2, -3]
[0, -1, -2, -2]
[0, -1, -2, -1]
[0, -1, -1, -2]
[0, -1, -1, -1]
[0, -1, -1, 0]
[0, -1, 0, -1]
[0, -1, 0, 0]
[0, -1, 0, 1]
[0, 0, -1, -2]
[0, 0, -1, -1]
[0, 0, -1, 0]
[0, 0, 0, -1]
[0, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 1, 0]
[0, 0, 1, 1]
[0, 0, 1, 2]
[0, 1, 0, -1]
[0, 1, 0, 0]
[0, 1, 0, 1]
[0, 1, 1, 0]
[0, 1, 1, 1]
[0, 1, 1, 2]
[0, 1, 2, 1]
[0, 1, 2, 2]
[0, 1, 2, 3]
以上です

[quickquip]

情報はこの欄にではなく、質問を編集して記載しましょう。

[yoshikazu.egawa]

質問を更新いたしました

[can110]

欲しいリストの生成規則が理解できません。
まずリストの数ですが
n=0：[0]の1通り
n=1：[0]の1通り×(-1,0,1)の3通り＝3通り
n=2：[0]の1通り×(-1,0,1)の3通り×(-2,-1,0,1,2)の5通り＝15通り
と考えたのですが、違いますよね？
n=2のときなぜ9通りでそれらのリストになるのかが分かりません。

[yoshikazu.egawa]

can110さんのご質問で「各リスト（行）の要素の数は、iの値に関係なく３個ではないでしょうか」にある通り、各要素の数は、その前の要素それぞれに対して3通りです。（生成規則としては、当該要素は、そのひとつ前の要素aに対して、(a-1, a, a+1)の3通りとなります、5通りとはなりません）
n=1：[0]の1通り
n=2：[0]の1通り×(-1,0,1)の3通り（3**(n-1)=3)
n=3：[0]の1通り×[1](-1,0,1)の3通り×（[1]の要素それぞれに対して）3通り＝9通りになります。(3**(n-1)=9）
n=4：[0]の1通り×[1](-1,0,1)の3通り×（[1]の要素それぞれに対して）3通り×（[2]の要素それぞれに対して）3通り＝27通りになります。
（3**(n-1)=27）

[yoshikazu.egawa]

質問を見直したら、「各要素aiの取りうる数値」のところに、誤りがあるのを発見しました。この間違いがご理解いただけなかった理由だと反省しています。申し訳ありませんでした。

[can110]

おそらく理解できました。それをもとに回答を修正しました。

Answer 1

再帰関数を使うとこうです。

def make_slist(n, zlist=None):
    if zlist == None:
        zlist = [0]
    if n == 1:
        return [zlist]
    else:
        plist = zlist.copy()
        nlist = zlist.copy()
        plist.append(zlist[-1]+1)
        nlist.append(zlist[-1]-1)
        zlist.append(0)
        return make_slist(n-1, plist)+make_slist(n-1, nlist)+make_slist(n-1, zlist)

実行結果

>>> make_slist(1)
[[0]]
>>> make_slist(2)
[[0, 1], [0, -1], [0, 0]]
>>> make_slist(3)
[[0, 1, 2], [0, 1, 0], [0, 1, 0], [0, -1, 0], [0, -1, -2], [0, -1, 0], [0, 0, 1], [0, 0, -1], [0, 0, 0]]
>>> make_slist(4)
[[0, 1, 2, 3], [0, 1, 2, 1], [0, 1, 2, 0], [0, 1, 0, 1], [0, 1, 0, -1], [0, 1, 0, 0], [0, 1, 0, 1], [0, 1, 0, -1], [0, 1, 0, 0], [0, -1, 0, 1], [0, -1, 0, -1], [0, -1, 0, 0], [0, -1, -2, -1], [0, -1, -2, -3], [0, -1, -2, 0], [0, -1, 0, 1], [0, -1, 0, -1], [0, -1, 0, 0], [0, 0, 1, 2], [0, 0, 1, 0], [0, 0, 1, 0], [0, 0, -1, 0], [0, 0, -1, -2], [0, 0, -1, 0], [0, 0, 0, 1], [0, 0, 0, -1], [0, 0, 0, 0]]

Comments

[yoshikazu.egawa]

ご回答をありがとうございました。
初めて質問をさせていただいた初学者ですが、これだけ多様な解があることに驚くとともに、遠い道のりだと感じています。勉強の参考にさせていただいてレベルアップを図っていきたいと思います。

Answer 2

もしかしたらもっと速い実装あるかもしれませんが…
生成規則をもとに素直に実装していけばよいです。
以下のように累積的に求めていけばよいです。

n = 3
ret_list = [[0]]
for i in range(1,n):
    new_list = []
    for one in ret_list:
        # ひとつ手前の要素の値に-1,+0,+1した要素を追加
        new_list.append( one + [one[i-1]-1])
        new_list.append( one + [one[i-1]])
        new_list.append( one + [one[i-1]+1])
    ret_list = new_list

print(*ret_list, sep='\n')
"""
n=2
[0, -1]
[0, 0]
[0, 1]
n=3
[0, -1, -2]
[0, -1, -1]
[0, -1, 0]
[0, 0, -1]
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[0, 1, 2]
n=4
[0, -1, -2, -3]
[0, -1, -2, -2]
[0, -1, -2, -1]
[0, -1, -1, -2]
[0, -1, -1, -1]
[0, -1, -1, 0]
[0, -1, 0, -1]
[0, -1, 0, 0]
[0, -1, 0, 1]
[0, 0, -1, -2]
[0, 0, -1, -1]
[0, 0, -1, 0]
[0, 0, 0, -1]
[0, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 1, 0]
[0, 0, 1, 1]
[0, 0, 1, 2]
[0, 1, 0, -1]
[0, 1, 0, 0]
[0, 1, 0, 1]
[0, 1, 1, 0]
[0, 1, 1, 1]
[0, 1, 1, 2]
[0, 1, 2, 1]
[0, 1, 2, 2]
[0, 1, 2, 3]
"""

以前の回答

iの場合の取りえる数値は-i～+iと表せるので以下でよいかと思います。

n = 5
slist = [list(range(-i,i+1)) for i in range(n)]

print(*slist, sep='\n')
"""
[0]
[-1, 0, 1]
[-2, -1, 0, 1, 2]
[-3, -2, -1, 0, 1, 2, 3]
[-4, -3, -2, -1, 0, 1, 2, 3, 4]
"""

Comments

[yoshikazu.egawa]

申し訳ありません。説明の仕方が悪かったのかもしれません。
たとえば、以下のような形で欲しいのです。（n=4の場合）
[0, -1, -2, -3]
[0, -1, -2, -2]
[0, -1, -2, -1]
[0, -1, -1, -2]
[0, -1, -1, -1]
[0, -1, -1, 0]
[0, -1, 0, -1]
[0, -1, 0, 0]
[0, -1, 0, 1]
[0, 0, -1, -2]
[0, 0, -1, -1]
[0, 0, -1, 0]
[0, 0, 0, -1]
[0, 0, 0, 0]
[0, 0, 0, 1]
（以下続きます）

[can110]

より単純なa2の場合はどうなりますか？
各リスト（行）の要素の数は、iの値に関係なく３個ではないでしょうか？

[yoshikazu.egawa]

その通りです。
質問を修正し、欲しいリストの具体的な事例を追加しました。

[yoshikazu.egawa]

ご回答ありがとうございました。
私のイメージにぴったりだったので、ベストアンサーとさせていただきました。私にとっての初めての質問でしたが、大勢の方から回答をいただけてうれしく思いました。いろいろな解を示していただいて、とても勉強になりました。

Answer 3

先頭の0は不要（情報がない）なので取り除いていいです。そうした方が見通しがよくなります。

まず[-1, 0, 1]でn個の直積を作ります。

>>> from itertools import product

>>> for x in product([-1, 0, 1], repeat=3):
...     print(list(x))
[-1, -1, -1]
[-1, -1, 0]
[-1, -1, 1]
[-1, 0, -1]
[-1, 0, 0]
[-1, 0, 1]
[-1, 1, -1]
[-1, 1, 0]
[-1, 1, 1]
[0, -1, -1]
[0, -1, 0]
[0, -1, 1]
[0, 0, -1]
[0, 0, 0]
[0, 0, 1]
[0, 1, -1]
[0, 1, 0]
[0, 1, 1]
[1, -1, -1]
[1, -1, 0]
[1, -1, 1]
[1, 0, -1]
[1, 0, 0]
[1, 0, 1]
[1, 1, -1]
[1, 1, 0]
[1, 1, 1]

例えばここから7番目の[-1, 1, -1]を取り出します。この列の第i項までの和を作ります。
第1項 -1
第2項 -1 + 1 = 0
第3項 -1 + 1 -1 = -1
これで[-1, 0, -1] という列ができました。

さて、質問の4要素の場合の7番目を見てください。[0, -1, 0, -1] でした。一致していますね?

質問の数列の構造はこのようになっています。

---

回答

>>> from itertools import accumulate,  product

>>> for x in product([-1, 0, 1], repeat=3):
...     print(list(accumulate(x)))
[-1, -2, -3]
[-1, -2, -2]
[-1, -2, -1]
[-1, -1, -2]
[-1, -1, -1]
[-1, -1, 0]
[-1, 0, -1]
[-1, 0, 0]
[-1, 0, 1]
[0, -1, -2]
[0, -1, -1]
[0, -1, 0]
[0, 0, -1]
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[0, 1, 2]
[1, 0, -1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[1, 2, 2]
[1, 2, 3]

Comments

[yoshikazu.egawa]

ご回答をありがとうございました。とてもシンプルな回答で驚きましたが、このシンプルな計算で、数学的になぜそうなるかについては、私の理解を超えていて今後勉強したいと思います。