Indeks permutasi terbalik

17

pengantar

Permutasi leksikografis dari daftar dengan elemen n dapat dinomori dari 0 hingga n ! - 1. Misalnya, 3! = 6 permutasi dari (1,2,3)akan (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).

Ketika permutasi diterapkan ke daftar, elemen-elemennya disusun dalam urutan yang sama dengan angka dalam permutasi. Sebagai contoh, menerapkan permutasi (2,3,1)ke l = (a,b,c)hasil (l[2],l[3],l[1]) = (b,c,a).

Kebalikan dari permutasi didefinisikan sebagai permutasi yang membalikkan operasi ini, yaitu menerapkan permutasi dan kemudian kebalikannya (atau sebaliknya) tidak mengubah array. Misalnya, kebalikannya (2,3,1)adalah (3,1,2), sejak menerapkannya pada (b,c,a)hasil (a,b,c).

Juga, kebalikan permutasi yang diterapkan pada permutasi itu sendiri menghasilkan bilangan bulat 1 ... n . Misalnya, menerapkan (3,1,2)untuk (2,3,1)hasil (1,2,3).

Kami sekarang mendefinisikan fungsi revind ( x ) sebagai indeks permutasi terbalik dari permutasi dengan indeks x . (Ini A056019 , jika Anda tertarik.)

Karena permutasi dengan indeks saya hanya memodifikasi item k terakhir dari daftar iff 0 ≤ i < k !, kita dapat menambahkan sejumlah elemen ke awal daftar tanpa mempengaruhi revind ( i ). Oleh karena itu panjang daftar tidak mempengaruhi hasilnya.

Tantangan

Tugas Anda adalah mengimplementasikan revind ( x ). Anda akan menulis program atau fungsi lengkap yang menggunakan satu integer nonnegatif x sebagai input / argumen dan menghasilkan / mengembalikan hasilnya sebagai integer nonnegatif tunggal.

Input dan output mungkin 0-diindeks atau 1-diindeks, tetapi ini harus konsisten di antara mereka.

Bawaan yang menghasilkan permutasi dengan indeks, mengembalikan indeks permutasi atau menemukan permutasi terbalik dilarang. (Builtin yang menghasilkan semua permutasi atau permutasi berikutnya diizinkan.)

Aturan standar berlaku.

Contohnya

Contoh di bawah ini adalah 0-diindeks.

Input    Output
0        0
1        1
2        2
3        4
4        3
5        5
6        6
13       10
42       51
100      41
1000     3628
2000     3974
10000    30593
100000   303016

Implementasi referensi (Python 3)

def revind(n):
    from math import factorial
    from itertools import permutations, count
    l = next(filter(lambda x: factorial(x) > n, count(1)))
    pms = list(permutations(range(l)))
    return [k for k in range(len(pms)) if tuple(pms[n][i] for i in pms[k]) == pms[0]][0]
PurkkaKoodari
sumber
1
Saya harus mencari definisi permutasi terbalik untuk memahami tantangan ini. Saya menemukan contoh Anda dengan (a,b,c)sangat tidak jelas. Harap sertakan penjelasan yang tepat tentang apakah permutasi terbalik itu.
Fatalkan
@Fatalize Ini agak sulit dijelaskan. Lebih baik sekarang?
PurkkaKoodari
Jelly memiliki atom (tingkat atas) yang mengurutkan indeks array dengan nilai yang sesuai. Ini terjadi untuk membalikkan permutasi 1, ..., n , tetapi itu tidak berfungsi untuk permutasi lainnya. Apakah built-in terlarang?
Dennis
@Dennis Pertanyaan sulit. Secara teknis, ia menemukan kebalikan dari permutasi apa pun setelah itu diterapkan ke daftar yang benar-benar meningkat. Karena itu saya akan mengatakan tidak diizinkan. (Jika seseorang benar-benar tidak setuju, silakan berkomentar. Saya dapat mengubah ini jika komunitas menginginkannya.)
PurkkaKoodari

Jawaban:

5

Jeli , 6 byte

ịŒ!⁺iR

I / O menggunakan pengindeksan berbasis 1. Sangat lambat dan haus akan memori.

Verifikasi

Selama input tidak melebihi 8! = 40320 , itu sudah cukup untuk mempertimbangkan semua permutasi dari array [1,…, 8] . Untuk kasus uji terakhir, permutasi [1,…, 9] sudah cukup.

Dengan kode yang sedikit dimodifikasi yang hanya mempertimbangkan permutasi dari 8 atau 9 bilangan bulat positif pertama, Anda dapat mencobanya secara online! atau verifikasi semua kasus uji yang tersisa .

Bagaimana itu bekerja

ịŒ!⁺iR  Main link. Argument: n

 Œ!     Yield all permutations of [1, ..., n].
ị       At-index; retrieve the n-th permutation.
   ⁺    Duplicate the Œ! atom, generating all permutations of the n-th permutation.
     R  Range; yield [1, ..., n].
    i   Index; find the index of [1, ..., n] in the generated 2D array.

Pendekatan alternatif, 6 byte (tidak valid)

Œ!Ụ€Ụi

Itu sama panjang dan menggunakan tingkat terlarang naik atom , tapi itu (bisa dibilang) lebih idiomatis.

Dengan mengawali 8 (atau 9 untuk test case terakhir), kita dapat mencobanya secara online!

Bagaimana itu bekerja

Œ!Ụ€Ụi  Main link. Argument: n

Œ!      Yield all permutations of [1, ..., n].
  Ụ€    Grade up each; sort the indices of each permutation by the corresponding
        values. For a permutation of [1, ..., n], this inverts the permutation.
    Ụ   Grade up; sort [1, ..., n!] by the corresponding inverted permutations
        (lexicographical order).
     i  Index; yield the 1-based index of n, which corresponds to the inverse of
        the n-th permutation.
Dennis
sumber
6

Mathematica, 74 byte

Max@k[i,Flatten@Outer[i=Permutations[j=Range@#];k=Position,{i[[#]]},j,1]]&

Menggunakan pengindeksan 1. Sangat tidak efisien. (menggunakan ~ 11GB memori saat inputnya11 )

Penjelasan

j=Range@#

Buat daftar dari 1 hingga N. Simpan di j.

i=Permutations[...]

Temukan semua permutasi dari j. Simpan itu di i.

k=Position

Simpan Positionfungsi di k. (untuk mengurangi byte-count saat menggunakan Positionlagi)

Flatten@Outer[...,{i[[#]]},j,1]

Temukan permutasi kebalikan dari permutasi ke-N.

Max@k[i,...]

Temukan k(Position ) dari permutasi terbalik di i(semua permutasi)

Menggunakan built-in, 46 43 byte

a[(a=Ordering)/@Permutations@Range@#][[#]]&

1-diindeks.

JungHwan Min
sumber
2
"Builtin yang ... menemukan permutasi terbalik dilarang"
Greg Martin
@GregMartin, ah, entah bagaimana saya melewatkan bagian itu dan hanya melihat bagian "mengembalikan indeks permutasi". Bodoh saya ... Kode baru tidak memiliki masalah itu.
JungHwan Min
ya, saya setuju itu mudah untuk dilewatkan. 74 byte — masih cukup mengesankan!
Greg Martin
5

MATL , 15 byte

:Y@tGY)Z)G:=!Af

Input dan output berbasis 1.

Mirip dengan jawaban CJam @ MartinEnder , tetapi menemukan permutasi terbalik dengan menyusun semua permutasi yang mungkin dengan yang ditentukan oleh input, dan melihat yang telah menjadi permutasi identitas.

Kehabisan memori dalam kompiler online untuk input 10 .

Cobalah online!

Penjelasan

:      % Implicitly input N. Push range [1 2 ... N]
Y@     % Matrix witll all permutations of size N. Each permutation is a row
tGY)   % Duplicate. Get the N-th row
Z)     % Use that as a column index into the matrix of all permutations
G:=    % Compare each row with [1 2 ... N]
!Af    % Find index of the row that matches. Implicitly display
Luis Mendo
sumber
5

Pyth, 12 byte

xJ.phQxL@JQh

Suite uji

0 diindeks.

Penjelasan:

xJ.phQxL@JQh
xJ.phQxL@JQhQ    Implicit variable introduction
                 Q = eval(input())
  .phQ           Form all permutations of range(Q+1), namely [0, 1, .. Q]
 J               Save to J.
        @JQ      Take the Qth element of J.
      xL   hQ    Map all elements of [0, 1, ..., Q] to their index in above
x                Find the index in J of the above.
isaacg
sumber
5

05AB1E , 14 13 byte

Memori sangat tidak efisien. Sekarang bahkan lebih banyak memori tidak efisien (tetapi lebih pendek 1 byte).
Kisaran berbasis 0.
Menggunakan pengodean CP-1252 .

ƒ¹ÝœD¹èNkˆ}¯k

Cobalah online! atau sebagai test suite yang dimodifikasi

Penjelasan

ƒ               # for N in range[0 .. x]
 ¹ÝœD           # generate 2 copies of all permutations of range[0 .. x]
     ¹è         # get permutation at index x
       Nkˆ      # store index of N in that permutation in global list
         }      # end loop
          ¯k    # get index of global list (inverse) in list of permutations
Emigna
sumber
4

CJam , 16 byte

ri_)e!_@=_$\f#a#

Indeks berbasis 0.

Cobalah online!

Saya tidak mendapatkan jauh lebih tidak efisien daripada ini ... kehabisan memori dengan pengaturan default Java untuk input lebih besar dari 8(tetapi bekerja pada prinsipnya untuk input sewenang-wenang diberikan jumlah yang cukup dari semesta waktu dan memori).

Penjelasan

ri    e# Read input and convert to integer N.
_)e!  e# Duplicate N, get all permutations of [0 1 ... N].
_@=   e# Duplicate permutations, get the Nth permutation.
_$    e# Duplicate and sort to get the sorted range [0 1 ... N].
\f#   e# For each of these values, get its index in the Nth permutation.
      e# This inverts the permutation.
a#    e# Find the index of this new permutation in the list of all permutations.
Martin Ender
sumber
3

GAP , 108 byte

h:=l->n->PositionProperty(l,p->l[n]*p=());
f:=n->h(Set(SymmetricGroup(First([1..n],k->Factorial(k)>=n))))(n);

1-diindeks. Baris baru tidak dihitung, tidak diperlukan. Saya tidak benar-benar harus menetapkan fungsi akhir ke sebuah nama, tapi ...

hadalah fungsi kari mengambil daftar permutasi dan indeks ke dalam daftar itu dan mengembalikan indeks permuasi terbalik. Tanpa batasan, saya hanya akan melakukannya Position(l,l[n]^-1). fmemanggil fungsi itu dengan permutasi yang diurutkan dari grup simetris yang cukup besar dan diberikann .

Saya hanya bisa menulis SymmetricGroup(n), lalu fungsinya dapat dihitung untuk nilai hingga 9. Karena sudah ada solusi yang jauh lebih kecil, saya lebih suka untuk dapat melakukan ini:

gap> f(100001);
303017

Solusi terindeks 0 yang sangat efisien yang berfungsi untuk argumen di bawah 99! (dan dapat digunakan untuk argumen di bawah 999! dengan biaya satu byte) adalah yang ini:

f:=function(n)
 local m,l,p,i,g;
 m:=First([1..99],k->Factorial(k)>n);
 g:=List([m-1,m-2..0],Factorial);
 l:=[1..m];
 p:=[];
 for i in g do
  Add(p,Remove(l,QuoInt(n,i)+1));
  n:=n mod i;
 od;
 return Sum(ListN(List([1..m],i->Number([1..Position(p,i)],j->p[j]>i)),g,\*));
end;

Setelah menghapus spasi putih, ini memiliki 255 byte.

Sievers Kristen
sumber
Kerja bagus! Saya berharap untuk mendapatkan beberapa solusi yang efisien juga.
PurkkaKoodari
3

JavaScript (ES6), 163 120 110 byte

f=(n,a=[],i=0,r=0,[j,...b]=a)=>n?a.splice(n%-~i,0,i)|f(n/++i|0,a,i):i?f(n,b,i-1,b.reduce((r,k)=>r+=k>j,r*i)):r
<input type=number min=0 oninput=o.textContent=f(+this.value)><pre id=o>

Diindeks 0. Bekerja dengan mengonversi indeks ke permutasi, membalikkannya, lalu mengonversi kembali ke indeks. Sunting: Disimpan sekitar 25% dengan membuat fpembalikan dan membalikkan permutasi, kemudian membuat gmengubah permutasi terbalik menjadi indeks. Menyimpan 10 byte lebih lanjut dengan menggabungkan dua panggilan rekursif menjadi satu fungsi. Tidak Disatukan:

function index(n) {
    var a = [0];
    for (var i = 1; n = Math.floor(n / i); i++) {
        var j = i - n % (i + 1);
        for (var k = 0; k < i; k++) {
            if (a[k] > j) a[k]++;
        }
        a.push(j);
    }
    a = [...a.keys()].map(k => a.indexOf(k));
    while (i) {
        n *= i--;
        j = a.pop();
        for (k = 0; k < i; k++) {
            if (a[k] > j) n++;
        }
    }
    return n;
}
Neil
sumber
1
@ JonathanAllan Maaf, saya pikir saya telah melihat penghematan 9-byte detik terakhir tapi saya gagal mengujinya secara menyeluruh. Saya telah kembali ke versi saya sebelumnya.
Neil
Implementasinya sangat desir sekarang.
Jonathan Allan
1
@JonathanAllan Ternyata menjadi lebih desir jika saya bisa fmembalikkan permutasi bukannya g...
Neil
3

J, 55 50 byte

g=:/:~i.@#
[:(#\.#.+/@(<{.)\.)@g(-i.)@>:g@g@,/@#:]

Berdasarkan esai J pada Indeks Permutasi .

Kode ini hanya membutuhkan memori sesuai urutan n tetapi menggunakan lebih banyak waktu karena kode ini mengurutkan waktu daftar ndan mencari nwaktu itu untuk setiap indeks.

Menggunakan builtin /: yang dapat menemukan tingkat daftar dan kebalikan dari permutasi, ada solusi 42 byte yang lebih efisien.

[:(#\.#.+/@(<{.)\.)@/:(-i.)@>:/:@/:@,/@#:]

Versi ini hanya membutuhkan 44 detik untuk menghitung test case terakhir jika dibandingkan dengan yang lainnya yang membutuhkan 105 detik.

Pemakaian

   g =: /:~i.@#
   f =: [:(#\.#.+/@(<{.)\.)@g(-i.)@>:g@g@,/@#:]
   (,.f"0) 0 1 2 3 4 5 6 13 42 100 1000 2000 10000
    0     0
    1     1
    2     2
    3     4
    4     3
    5     5
    6     6
   13    10
   42    51
  100    41
 1000  3628
 2000  3974
10000 30593
   timex 'r =: f 100000'
105.787
   r
303016
mil
sumber
+1 untuk efisiensi memori yang tidak dapat disentuh oleh bahasa-bahasa golf.
Magic Octopus Mm
2

Jelly , 14 13 9 byte

-4 byte terima kasih kepada @Dennis (yang dia mainkan lebih jauh menggunakan quick dalam jawabannya )

Œ!ịịŒ!$iR

Implementasi lain yang sangat lambat.
Pengindeksan berbasis 1 digunakan di sini, jadi hasil yang diharapkan adalah:

input:  1 2 3 4 5 6 7 8  9 10 11
output: 1 2 3 5 4 6 7 8 13 19  9

Tidak ada gunanya bahkan memasang tautan IDE online, karena TIO membunuh pada input 10. Hasil lokal (terakhir sangat lambat dan membutuhkan satu ton memori!):

C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 1
1
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 2
2
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 3
3
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 4
5
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 5
4
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 6
6
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 7
7
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 8
8
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 9
13
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 10
19
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 11
9

Bagaimana?

Œ!ịịŒ!$iR - Main link 1: n
      $   - last two links as a monad
    Œ!    -     permutations of implicit range [1,2,3,...,n]
   ị      -     value at index n (the nth permutation)
Œ!        - permutations of implicit range [1,2,3,...,n]
  ị       - value at index (the indexes of the permuted values in the nth permutation)
       i  - index of
        R - range [1,2,3,...,n]

Catatan: tidak perlu mengurutkan permutasi karena kami menggunakan urutan yang sama untuk menemukan permutasi dan dan itu terbalik.

Jonathan Allan
sumber
Tidak dapat mengujinya dari ponsel saya, tetapi tidak bisakah Anda menyingkirkan tautan 2 dan membuatnya menjadi yang utama ÇịịÇ$iR?
Dennis
Sebenarnya, yang Rsebelumnya Œ!adalah implisit, jadi Œ!ịịŒ!$iRharus melakukan pekerjaan.
Dennis
Ya, ini adalah entri yang sangat terburu-buru sebelum bertemu teman.
Jonathan Allan
2

Python 2, 116 114 byte

from itertools import*
def f(n):r=range(n+1);l=list(permutations(r));print l.index(tuple(l[n].index(v)for v in r))

repl.it

Berbasis 0. Lambat dan memori haus tetapi kekurangan byte.


Tidak menggunakan fungsi permutasi; baik memori dan waktu efisien. 289 285 byte

-4 byte terima kasih kepada @Christian Sievers (permutasi penuh sudah terbentuk)

h=lambda n,v=1,x=1:v and(n>=v and h(n,v*x,x+1)or(v,x-1))or n and h(n-1,0,n*x)or x
i=lambda p,j=0,r=0:j<len(p)and i(p,j+1,r+sum(k<p[j]for k in p[j+1:])*h(len(p)-j-1,0))or r
def f(n):t,x=h(n);g=range(x);o=g[:];r=[];exec"t/=x;x-=1;r+=[o.pop(n/t)];n%=t;"*x;return i([r.index(v)for v in g])

Saya tahu ini kode golf tetapi saya pikir @ Pietu1998 tertarik pada implementasi yang efisien juga.

Lihat beraksi di repl.it

Meskipun ini menggunakan lebih banyak byte daripada perbandingan implementasi referensi untuk n=5000000:

ref:    6GB 148s  
this: 200KB <1ms

f adalah fungsi indeks terbalik.

fpertama mendapatkan faktorial berikutnya di atas n,, tdan bilangan bulat yang faktorialnya adalah, xdengan memanggil h(n), dan set g=range(x), item yang akan membentuk permutasi,o=g[:] ,, dan pemegang permutasi,r=[]

Selanjutnya itu membangun permutasi pada indeks ndengan popmemasukkan indeks dari representasi basis faktorial npada gilirannya dari item o,, dan menambahkannya r. Representasi dasar faktorial ditemukan oleh div dan mod ndengan di tmana tdiv'd oleh xdan xturun ke 1.

Akhirnya ia menemukan indeks permutasi terbalik dengan memanggil idengan permutasi terbalik,[r.index(v)for v in g]

h adalah fungsi tujuan ganda untuk menghitung faktorial dari bilangan non-negatif atau menghitung faktorial berikutnya di atas bilangan non-negatif dan bilangan bulat yang membuat faktorial itu.

Dalam keadaan default v=1dan melakukan yang terakhir dengan mengalikan vdengan x(juga awalnya 1) dan menambah xsampai nsetidaknya sama besar, lalu kembali vdanx-1 dalam tupel.

Untuk menghitung n!satu panggilan h(n,0)yang kelipatan x(awalnya 1) oleh ndan decrements nsampai nadalah 0ketika pengembalianx .

imemberikan indeks leksikografis permutasi,, pdari item [0,1,...n]dengan menjumlahkan produk faktorial dari basis faktorial setiap indeks h(len(p)-j-1,0),, dan berapa banyak item di sebelah kanan indeks kurang dari nilai pada indeks itu sum(k<p[j]for k in p[j+1:]),.

Jonathan Allan
sumber
Saya pikir Anda tidak perlu untuk kasus khusus item terakhir ketika membangun permutasi. Saya tidak dalam solusi GAP 255 byte saya.
Christian Sievers
Saya menambahkannya secara terpisah di akhir karena kalau tidak akan ada pembagian dengan kesalahan nol ketika itu terjadi t/=x.
Jonathan Allan
Butuh beberapa saat untuk melihat: loop sudah melakukan semuanya, Anda dapat menggantinya (r+o)dengan r.
Christian Sievers
Anda benar! Terima kasih banyak.
Jonathan Allan
1

Python 2, 130 129 byte

p=lambda x,k,j=1:x[j:]and p(x,k/j,j+1)+[x.pop(k%j)]
n=input();r=range(n+2);k=0
while[p(r*1,n)[i]for i in p(r*1,k)]>r:k+=1
print k
Dennis
sumber
1

Sebenarnya , 18 11 byte

Jawaban ini menggunakan algoritme dalam jawaban Dennis 'Jelly tetapi diindeks 0. Selamat datang saran bermain golf! Cobalah online!

4╞r;)╨E╨♂#í

Tidak melakukanolf

      Implicit input n.
4╞    Push 4 duplicates of n. Stack: n, n, n, n
r;)   Push the range [0...n], and move a duplicate of that range to BOS for later.
╨E    Push the n-length permutations of [0...n] and get perm_list[n].
        Stack: perm_list[n], n, [0...n]
╨     Push the n-length permutations of perm_list[n].
♂#    Convert every "list" in the zip to an actual list.
        Stack: perm(perm_list[n]), [0...n]
í     Get the index of [0...n] in the list of permutations of perm_list[n].
      Implicit return.
Sherlock9
sumber