Pertanyaan Jumlah minimal swap yang diperlukan untuk mengubah Array 1 ke Array 2?


Misalnya, input adalah

Array 1 = [2, 3, 4, 5]
Array 2 = [3, 2, 5, 4]

Jumlah minimum swap yang dibutuhkan 2.

Swap tidak harus dengan sel-sel yang berdekatan, setiap dua elemen dapat bertukar.


32
2018-06-07 07:00


asal


Jawaban:


Seperti @IVlad dicatat dalam komentar untuk pertanyaan Anda Masalah yodaness meminta Anda untuk menghitung jumlah inversi dan bukan jumlah swap minimal.

Sebagai contoh:

L1 = [2,3,4,5]
L2 = [2,5,4,3]

Jumlah minimal swap adalah satu (tukar 5 dan 3 masuk L2 mendapatkan L1), tetapi jumlah inversi adalah tiga: (5 4), (5 3), dan (4 3) pasangan berada dalam urutan yang salah.

Cara paling sederhana untuk menghitung jumlah inversi mengikuti dari definisi:

Sepasang elemen (halsaya, halj) disebut inversi dalam permutasi p jika i <j dan psaya > pj.

Dengan Python:

def count_inversions_brute_force(permutation):
    """Count number of inversions in the permutation in O(N**2)."""
    return sum(pi > permutation[j]
               for i, pi in enumerate(permutation)
               for j in xrange(i+1, len(permutation)))

Anda bisa menghitung inversi O(N*log(N)) menggunakan strategi membagi & menaklukkan (mirip dengan bagaimana algoritma penggabungan semacam bekerja). Ini pseudo-code dari Menghitung Inversi diterjemahkan ke kode Python:

def merge_and_count(a, b):
    assert a == sorted(a) and b == sorted(b)
    c = []
    count = 0
    i, j = 0, 0
    while i < len(a) and j < len(b):
        c.append(min(b[j], a[i]))
        if b[j] < a[i]:
            count += len(a) - i # number of elements remaining in `a`
            j+=1
        else:
            i+=1
    # now we reached the end of one the lists
    c += a[i:] + b[j:] # append the remainder of the list to C
    return count, c

def sort_and_count(L):
    if len(L) == 1: return 0, L
    n = len(L) // 2 
    a, b = L[:n], L[n:]
    ra, a = sort_and_count(a)
    rb, b = sort_and_count(b)
    r, L = merge_and_count(a, b)
    return ra+rb+r, L

Contoh:

>>> sort_and_count([5, 4, 2, 3])
(5, [2, 3, 4, 5])

Berikut solusinya dengan Python untuk contoh dari masalah:

yoda_words   = "in the force strong you are".split()
normal_words = "you are strong in the force".split()
perm = get_permutation(normal_words, yoda_words)
print "number of inversions:", sort_and_count(perm)[0]
print "number of swaps:", number_of_swaps(perm)

Keluaran:

number of inversions: 11
number of swaps: 5

Definisi dari get_permutation() dan number_of_swaps() adalah:

def get_permutation(L1, L2):
    """Find permutation that converts L1 into L2.

    See http://en.wikipedia.org/wiki/Cycle_representation#Notation
    """
    if sorted(L1) != sorted(L2):
        raise ValueError("L2 must be permutation of L1 (%s, %s)" % (L1,L2))

    permutation = map(dict((v, i) for i, v in enumerate(L1)).get, L2)
    assert [L1[p] for p in permutation] == L2
    return permutation

def number_of_swaps(permutation):
    """Find number of swaps required to convert the permutation into
    identity one.

    """
    # decompose the permutation into disjoint cycles
    nswaps = 0
    seen = set()
    for i in xrange(len(permutation)):
        if i not in seen:           
           j = i # begin new cycle that starts with `i`
           while permutation[j] != i: # (i σ(i) σ(σ(i)) ...)
               j = permutation[j]
               seen.add(j)
               nswaps += 1

    return nswaps

27
2018-06-07 12:15



Seperti tersirat oleh solusi Sebastian, algoritma yang Anda cari dapat didasarkan pada pemeriksaan siklus permutasi.

Kita harus mempertimbangkan array # 2 untuk menjadi transformasi permutasi pada array # 1. Dalam contoh Anda, permutasi dapat direpresentasikan sebagai P = [2,1,4,3].

Setiap permutasi dapat dinyatakan sebagai satu set siklus disjoint, mewakili perubahan posisi siklik dari item. Permutasi P misalnya memiliki 2 siklus: (2,1) dan (4,3). Oleh karena itu, dua swap sudah cukup. Dalam kasus umum, Anda harus mengurangi jumlah siklus dari panjang permutasi, dan Anda mendapatkan jumlah minimum swap yang diperlukan. Ini mengikuti dari pengamatan bahwa untuk "memperbaiki" siklus elemen N, N-1 swap sudah cukup.


10
2018-06-07 18:40



Masalah ini memiliki solusi yang bersih, serakah, dan sepele:

  1. Temukan operasi swap mana saja yang didapat kedua bertukar elemen di Array1 lebih dekat ke tujuan mereka di Array2. Lakukan operasi swap pada Array1 jika ada.
  2. Ulangi langkah 1 hingga tidak ada lagi operasi swap seperti itu.
  3. Temukan operasi swap mana saja yang didapat satu bertukar elemen di Array1 lebih dekat ke tujuannya di Array2. Jika operasi semacam itu ada, lakukan pada Array1.
  4. Kembali ke langkah 1 hingga Array1 == Array2.

Ketepatan dari algoritma dapat dibuktikan dengan mendefinisikan potensi masalah sebagai penjumlahan jarak dari semua elemen dalam array1 dari tujuan mereka dalam array2.


3
2018-06-09 14:23



Mungkin ada beberapa solusi pemrograman dinamis yang cerdas tetapi saya tidak bisa mengetahuinya sekarang. Anda bisa melakukan traversal BFS naif menggunakan sesuatu seperti ini:

  • menegaskan bahwa itu mungkin (misalnya dengan menyortir dan membandingkan)
  • Queue q = [(0, L1)]
  • Sedangkan q tidak kosong
    • ekstrak beberapa pasangan (i, L)
    • jika L == L2, kembalikan i
    • untuk masing-masing 0 <= i, j <= L1.length
      • tambahkan (i + 1, L.swap (i, j)) ke q

MEMPERBARUI: implementasi dengan Python (lambat O ((N3)n))

def bfs(L1, L2):
    assert sorted(L1) == sorted(L2)
    q = deque([ (0,L1) ])
    while q:
        n, L = q.popleft()
        if L == L2: return n
        for i, j in combinations(range(len(L1)), 2): # all N*(N-1)/2 pairs
            q.append((n+1, swap(L, i, j)))

from collections import deque
from itertools   import combinations    

def swap(L, i, j):
    a = list(L) # make copy
    a[i], a[j] = a[j], a[i] # swap
    return a

1
2018-06-07 07:25



Ini dapat dengan mudah dikonversi ke jenis masalah lain, yang dapat diselesaikan dengan lebih efisien. Semua yang diperlukan adalah mengonversi array menjadi permutasi, yaitu mengubah nilai ke id mereka. Jadi larik Anda:

L1 = [2,3,4,5]
L2 = [2,5,4,3]

akan menjadi

P1 = [0,1,2,3]
P2 = [0,3,2,1]

dengan tugas 2->0, 3->1, 4->2, 5->3. Ini hanya dapat dilakukan jika tidak ada item yang diulang. Jika ada, maka ini menjadi lebih sulit untuk dipecahkan.

Mengubah permutasi dari satu ke yang lain dapat dikonversi ke masalah yang serupa (Jumlah swap dalam permutasi) dengan membalikkan permutasi target di O (n), menyusun permutasi dalam O (n) dan kemudian menemukan jumlah swap dari sana ke permutasi identitas di O (m). Diberikan:

int P1[] = {0, 1, 2, 3}; // 2345
int P2[] = {0, 3, 2, 1}; // 2543

// we can follow a simple algebraic modification
// (see http://en.wikipedia.org/wiki/Permutation#Product_and_inverse):
// P1 * P = P2                   | premultiply P1^-1 *
// P1^-1 * P1 * P = P1^-1 * P2
// I * P = P1^-1 * P2
// P = P1^-1 * P2
// where P is a permutation that makes P1 into P2.
// also, the number of steps from P to identity equals
// the number of steps from P1 to P2.

int P1_inv[4];
for(int i = 0; i < 4; ++ i)
    P1_inv[P1[i]] = i;
// invert the first permutation in O(n)

int P[4];
for(int i = 0; i < 4; ++ i)
    P[i] = P2[P1_inv[i]];
// chain the permutations in O(n)

int num_steps = NumSteps(P, 4); // will return 2
// now we just need to count the steps in O(num_steps)

Untuk menghitung langkah-langkah, algoritme sederhana dapat dibuat, seperti:

int NumSteps(int *P, int n)
{
    int count = 0;
    for(int i = 0; i < n; ++ i) {
        for(; P[i] != i; ++ count) // could be permuted multiple times
            swap(P[P[i]], P[i]); // look where the number at hand should be
    }
    // count number of permutations

    return count;
}

Ini selalu menukar item untuk tempat di mana seharusnya di permutasi identitas, oleh karena itu pada setiap langkah itu undoes dan jumlah satu swap. Sekarang, asalkan jumlah swap yang dikembalikan memang minimum, runtime dari algoritma dibatasi olehnya dan dijamin akan selesai (bukannya terjebak dalam loop tak terbatas). Ini akan berjalan di O(m) swap atau O(m + n) iterasi loop di mana m adalah jumlah swap (the count kembali) dan n adalah jumlah item dalam urutan (4). Perhatikan itu m < n selalu benar. Karena itu, ini harus lebih unggul O(n log n) solusi, karena batas atas adalah O(n - 1) swap atau O(n + n - 1) iterasi loop di sini, yang praktis O(n) (faktor konstan 2 dihilangkan dalam kasus terakhir).

Algoritme hanya akan bekerja untuk permutasi yang valid, ia akan mengulang tanpa batas untuk urutan dengan nilai duplikat dan akan melakukan out-of-bounds array access (dan crash) untuk urutan dengan nilai selain [0, n). Sebuah test case lengkap dapat ditemukan sini (dibangun dengan Visual Studio 2008, algoritma itu sendiri harus cukup portabel). Ini menghasilkan semua permutasi yang memungkinkan dari panjang 1 sampai 32 dan memeriksa solusi, yang dihasilkan dengan pencarian pertama yang luas (BFS), tampaknya bekerja untuk semua permutasi dari panjang 1 sampai 12, kemudian menjadi cukup lambat tetapi saya menganggap itu hanya akan terus bekerja .


1
2017-07-21 07:13



Ini sepertinya sebuah edit jarak masalah, kecuali bahwa hanya transposisi yang diizinkan.

Periksa Jarak Damerau-Levenshtein kode semu. Saya yakin Anda dapat menyesuaikannya untuk menghitung hanya transposisi.


0
2018-06-07 07:28



Algoritma:

  1. Periksa apakah unsur-unsur daftar dalam posisi yang sama adalah sama. Jika ya, tidak diperlukan swap. Jika tidak, tukar posisi elemen daftar di mana pun elemen tersebut cocok
  2. Iterate proses untuk seluruh elemen daftar.

Kode:

def nswaps(l1, l2):
    cnt = 0
    for i in range(len(l1)):
        if l1[i] != l2[i]:
            ind = l2.index(l1[i])
            l2[i], l2[ind] = l2[ind], l2[i]
            cnt += 1
        pass
    return cnt

0
2017-11-08 15:46



@ J.F. Jawaban Sebastian dan @Eyal Schneider cukup keren. Saya terinspirasi untuk memecahkan masalah yang sama: Hitung swap minimum yang diperlukan untuk mengurutkan array, misalnya: untuk mengurutkan {2,1,3,0}, Anda perlu minimal 2 swap.

Berikut ini adalah Kode Java:

// 0 1 2 3
// 3 2 1 0  (0,3) (1,2)
public static int sortWithSwap(int [] a) {
    Integer[] A = new Integer[a.length];
    for(int i=0; i<a.length; i++)   A[i] = a[i];
    Integer[] B = Arrays.copyOf(mapping(A), A.length, Integer[].class);

    int cycles = 0;
    HashSet<Integer> set = new HashSet<>();
    boolean newCycle = true;
    for(int i=0; i<B.length; ) {
        if(!set.contains(B[i])) {
            if(newCycle) {
                newCycle = false;
                cycles++;
            }
            set.add(B[i]);
            i = B[i];
        }
        else if(set.contains(B[i])) {   // duplicate in existing cycles
            newCycle = true;
            i++;
        }
    }

    // suppose sequence has n cycles, each cycle needs swap len(cycle)-1 times
    // and sum of length of all cycles is length of sequence, so
    // swap = sequence length - cycles
    return a.length - cycles;
}

// a b b c
// c a b b
// 3 0 1 1
private static Object[] mapping(Object[] A) {
    Object[] B = new Object[A.length];
    Object[] ret = new Object[A.length];
    System.arraycopy(A, 0, B, 0, A.length);
    Arrays.sort(A);
    HashMap<Object, Integer> map = new HashMap<>();
    for(int i=0; i<A.length; i++) {
        map.put(A[i], i);
    }

    for(int i=0; i<B.length; i++) {
        ret[i] = map.get(B[i]);
    }
    return ret;
}

-1
2018-06-04 03:52