Encoding set permutasi dengan set pembangkit dan set elemen yang dikecualikan

Algoritma polinomial-waktu dikenal untuk menemukan set yang menghasilkan kelompok permutasi, yang menarik karena kita kemudian dapat mewakili kelompok-kelompok tersebut secara ringkas tanpa menyerah pada algoritma polinomial-waktu untuk menjawab banyak pertanyaan menarik terkait dengan kelompok-kelompok ini.

Namun, kadang-kadang kita mungkin tertarik pada set permutasi yang tidak membentuk grup, sehingga set tersebut akan diwakili oleh , di mana adalah grup yang dihasilkan oleh set dari generator dan adalah satu set permutasi yang tidak dalam , bukan hanya .$R$$R=\langle S\rangle \setminus T$$\langle S\rangle$$S$$T$$R$$\langle S\rangle$

Apakah ada pekerjaan yang dilakukan pada komputasi pengkodean seperti itu dalam bentuk pasangan , mungkin dengan tujuan alami tambahan untuk meminimalkan?$\{S,T\}$$|S|+|T|$

Jika Anda menyimpan permutasi acak dengan probabilitas maka Anda akan membutuhkanlog2(n!)Bit per permutasi, Kolmogorov kompleksitas perintah itu.${1\over2}$$log_{2}(n!)$

Jika distribusinya non-acak, itu tergantung.

$S_{n}$

$log_{2}( OEIS\_A186202(n) )$$log_{2}(n!)$