Hasilkan rangkaian leksikografis secara efisien dengan Python

Algoritma yang sangat efektif diadaptasi dari buku Jorg Arndt "Matters Computational"
(Bab 7.2 Co-lexicographic order for compositions into exactly k parts)

n = 4
k = 3

x = [0] * n
x[0] = k

while True:
    print(x)
    v = x[-1]
    if (k==v ):
        break
    x[-1] = 0
    j = -2
    while (0==x[j]):
        j -= 1
    x[j] -= 1
    x[j+1] = 1 + v

[3, 0, 0, 0]
[2, 1, 0, 0]
[2, 0, 1, 0]
[2, 0, 0, 1]
[1, 2, 0, 0]
[1, 1, 1, 0]
[1, 1, 0, 1]
[1, 0, 2, 0]
[1, 0, 1, 1]
[1, 0, 0, 2]
[0, 3, 0, 0]
[0, 2, 1, 0]
[0, 2, 0, 1]
[0, 1, 2, 0]
[0, 1, 1, 1]
[0, 1, 0, 2]
[0, 0, 3, 0]
[0, 0, 2, 1]
[0, 0, 1, 2]
[0, 0, 0, 3]

Jumlah komposisi dan waktu dalam hitungan detik untuk Python biasa (mungkin array numpy lebih cepat) untuk n=100, dan k = 2,3,4,5 (2,8 ghz Cel-1840)

2  5050 0.040000200271606445
3  171700 0.9900014400482178
4  4421275 20.02204465866089
5  91962520 372.03577995300293
I expect time  2 hours for 100/6 generation

Sama dengan array numpy (x = np.zeros((n,), dtype=int)) memberikan hasil yang lebih buruk - tetapi mungkin karena saya tidak tahu cara menggunakannya dengan benar

2  5050 0.07999992370605469
3  171700 2.390003204345703
4  4421275 54.74532389640808

Kode asli (ini Delphi, kompiler C/C++ mungkin mengoptimalkan lebih baik) menghasilkan 100/6 dalam 21 detik

3  171700  0.012
4  4421275  0.125
5  91962520  1.544
6  1609344100 20.748

Tidak bisa tidur sampai semua pengukuran belum selesai :)

MSVS VC++: 18 detik! (optimasi O2)

5  91962520 1.466
6  1609344100 18.283

Jadi 100 juta varian per detik. Banyak waktu yang terbuang untuk memeriksa sel yang kosong (karena rasio pengisiannya kecil). Kecepatan yang dijelaskan oleh Arndt dicapai pada rasio k/n yang lebih tinggi dan sekitar 300-500 juta varian per detik:

n=25, k=15 25140840660 60.981  400 millions per second

Rekomendasi saya:

1. Tulis ulang sebagai generator menggunakan yield, bukan loop yang menggabungkan variabel global pada setiap iterasi.
2. Pertahankan jumlah yang berjalan alih-alih menghitung jumlah beberapa subset representasi array dari angka tersebut.
3. Operasikan satu contoh representasi nomor kerja Anda alih-alih menggabungkan salinannya ke variabel sementara pada setiap iterasi.

Perhatikan bahwa tidak ada urutan tertentu yang tersirat.

Saya punya solusi yang lebih baik menggunakan itertools sebagai berikut,

from itertools import product
n = 4 #number of elements
s = 3 #sum of elements
r = []
for x in range(n):
    r.append(x)
result = [p for p in product(r, repeat=n) if sum(p) == s]
print(len(result))
print(result)

Saya mengatakan ini lebih baik karena sistem saya membutuhkan waktu 0,1 detik, sedangkan kode Anda dengan numpy membutuhkan waktu 0,2 detik.

Tetapi sejauh n=100 dan s=6, kode ini membutuhkan waktu untuk melewati semua kombinasi, menurut saya perlu waktu berhari-hari untuk menghitung hasilnya.

Saya juga menemukan solusi menggunakan itertools (Sumber: https://bugs.python.org/msg144273 ). Kode berikut:

import itertools
import operator

def combinations_with_replacement(iterable, r):
    # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
    pool = tuple(iterable)
    n = len(pool)
    if not n and r:
        return
    indices = [0] * r
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != n - 1:
                break
        else:
            return
        indices[i:] = [indices[i] + 1] * (r - i)
        yield tuple(pool[i] for i in indices)

int_part = lambda n, k: (tuple(map(c.count, range(k))) for c in combinations_with_replacement(range(k), n))
for item in int_part(3,4): print(item)