質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
86.12%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

解決済

条件を満たす(n)個の要素を持つリストを全パターン生成したいです。

keiji_kc
keiji_kc

総合スコア18

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

2回答

0リアクション

2クリップ

560閲覧

投稿2022/11/18 04:58

やりたいこと

  • pythonで 条件を満たす(n)個の要素を持つリストを全パターン生成したいです。

例えば、以下のような結果を取得したいです。

[[1, 1, 1, 1, 1, 1, 1, 2, 2, 2], [0, 1, 1, 1, 1, 1, 1, 2, 2, 2], [0, 0, 1, 1, 1, 1, 1, 2, 2, 2], .....]

生成するリストの条件

  • 要素数 n=10 (実際には数を50個以上に増やしたい)
  • 各要素は0,1,2からなります。
  • 0は3個以下しか含まれない。(nの数が大きくなると、この数字も増やします。例えば、int(n*0.1)個程度。)
  • 2も3個以下しか含まれない。(同上)

n=10の場合、3**10パターンから、0と2を一定数以上含むパターンのリストを削除するイメージです。

n=15程度なら、実現できる処理は以下のように書きました。

python

from itertools import product pattern = [] n = 10 # 何列の結果を出すか(n=20くらいでメモリーエラーになる。) for _ in range(n): pattern.append([0,1,2]) data = list(product(*pattern)) # この処理が重いです。 # dataは、例えば、例: [[0, 0, 1, 1, 1, 1, 1, 2, 2, 2], [0, 1, 1, 1, 1, 1, 1, 2, 2, 2].....]のようなデータです。 # dataから(ここでは例として)、"0が3個以上"、"2が3個以上"含むリストを、削除します。 result = [] for row in data: if row.count(0) >= 3 or row.count(2) >= 3: continue result.append(row) print(resutl)

この方法ですと、nが大きくなると計算しきれずメモリーエラーになってしまいます。n=10(310)ではすぐに計算できても、20では(320)で手元のPCではエラーを起こします。

ただ、例えば、n=10で計算した場合に、総当りで出したdataは59049個のなのに対して、必要なデータをピックアップしたresultは2181個と相当少なくなります。なので、総当たりせずに、resultを直接出せれば、nが大きくなってもある程度なら計算できるのでは?と考えています。

この処理の中で最も重いのは、

data = list(product(*pattern))

です。
ここで総当りしてしまっているのが無駄な作業で、0や2を含む数が規定より多い場合に、処理をしないようにスキップできればいいはずです。

仮説

例えば、

  • はじめに[1,1,1,1,1,1...]を作って、0をn個、2をm個、代入する、という発想もありなのかな?と考えはしたものの、コードに落とし込めません。。
  • ビット演算を使う??
  • numpyで処理すれば多少は早くなる?

ただ、正解にたどり着けません。。。

教えて頂けると幸いです。

以下のような質問にはリアクションをつけましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

リアクションが多い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

まだ回答がついていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
86.12%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。