Saya ingin mendapatkan daftar semua permutasi atau peringkat permutasi di mana elemen ith adalah k dan len lebih besar dari k dan diberi label dengan n. Daftar bilangan bulat dari 1..n harus diizinkan. Bagaimana ini bisa dilakukan?

Untuk Elemen pertama dari permutasi itu sepele. Tapi bagaimana cara kerjanya untuk Elemen ith? Iterasi melalui n! permutasi bukanlah suatu pilihan.

-1
TTho Einthausend 22 Januari 2020, 01:58

2 jawaban

Jawaban Terbaik

Pertama-tama, perhatikan bahwa masalah ini dapat dengan mudah diubah menjadi permutasi peringkat/daftar saja. Yang perlu Anda lakukan hanyalah menulis fungsi yang mengambil permutasi 1..(n-1) dan mengubahnya menjadi permutasi yang memenuhi kondisi Anda, dan sebaliknya. (Ke satu arah cukup tambahkan setiap angka dalam permutasi yang lebih besar dari k dan masukkan k di posisi ke i. Ke arah lain hapus k dan kurangi semuanya lebih besar dari k.)

Tetapi peringkat/daftar adalah masalah yang dipahami dengan baik. Lihat https://rosettacode.org/wiki/Permutation/Rank_of_a_permutation untuk solusi dalam berbagai bahasa, termasuk tiga dengan Python.

Gagasan ini dapat diperluas ke lebih banyak kondisi seperti yang pertama. Anda hanya perlu menulis transformasi yang lebih umum terlebih dahulu.

1
btilly 22 Januari 2020, 03:03

Peringatan: panjang permutations adalah (n-1)!, dan ukuran total permutations adalah O(n*(n-1)!).

import itertools
i,k,n = 1,5,10 #pick these
permutations = [p for p in itertools.permutations(list(range(1,n+1,1))) if p[i]==k]
0
Mark Snyder 21 Januari 2020, 23:16