Menghasilkan Kombinasi dari serangkaian pasangan tanpa pengulangan elemen

28

Saya memiliki satu set pasangan. Setiap pasangan berbentuk (x, y) sedemikian rupa sehingga x, y milik bilangan bulat dari kisaran [0,n).

Jadi, jika n adalah 4, maka saya memiliki pasangan berikut:

(0,1) (0,2) (0,3)
(1,2) (1,3) 
(2,3) 

Saya sudah memiliki pasangan. Sekarang, saya harus membangun kombinasi menggunakan n/2pasangan sehingga tidak ada bilangan bulat yang diulang (dengan kata lain, setiap bilangan bulat muncul setidaknya sekali dalam kombinasi akhir). Berikut ini adalah contoh kombinasi yang benar dan salah untuk pemahaman yang lebih baik

 1. (0,1)(1,2) [Invalid as 3 does not occur anywhere]
 2. (0,2)(1,3) [Correct]
 3. (1,3)(0,2) [Same as 2]

Dapatkah seseorang menyarankan saya cara untuk menghasilkan semua kombinasi yang mungkin, begitu saya memiliki pasangan.

Ankit
sumber
Mungkin dengan menggunakan array 2d untuk mewakili pasangan Anda. Kombinasi yang valid sesuai dengan pilihan sel array n sehingga setiap baris dan kolom mengandung tepat 1 sel yang dipilih.
Joe
4
Apakah Anda mengatakan bahwa input adalah himpunan semua pasangan? Jika demikian, maka Anda harus mengatakan bahwa inputnya hanya . n
rgrig
2
Apakah selalu seimbang? Jika tidak, pernyataan "tidak ada bilangan bulat yang diulang" dan "setiap bilangan bulat muncul setidaknya satu kali dalam kombinasi akhir" saling bertentangan. n
Dmytro Korduban
1
masalah yang sama dengan @rgrig: apakah semua input pasangan unordered atau apakah set pasangan sewenang-wenang yang mungkin? Jika semuanya berpasangan maka Anda bisa mengatakan inputnya adalah , tidak perlu memberikan daftar. n
Kaveh
1
Anda tertarik untuk menghasilkan semua kecocokan grafik yang sempurna pada poin yang ditentukan oleh set pasangan awal Anda. Terlebih lagi tampaknya Anda menganggap grafik itu sebagai grafik lengkap pada titik-titik itu. Pertanyaan Anda akan lebih jelas jika Anda menyebutkannya. Ada pencocokan tersebut. ( n - 1 ) ! ! : = 1 × 3 × 5 × × ( n - 1 )n(n1)!!:=1×3×5××(n1)
Marc van Leeuwen

Jawaban:

14

Salah satu cara langsung adalah prosedur rekursif yang melakukan hal berikut pada setiap doa. Input ke prosedur adalah daftar pasangan yang telah dipilih dan daftar semua pasangan.

  1. Hitung angka terkecil yang belum tercakup oleh daftar input. Untuk permohonan pertama, ini akan menjadi 0 tentu saja, karena tidak ada pasangan yang dipilih.
  2. Jika semua angka tercakup, Anda memiliki kombinasi yang benar, cetak dan kembalikan langkah sebelumnya. Kalau tidak, angka terkecil yang terungkap adalah target yang akan kita tuju.
  3. Cari melalui pasangan mencari cara untuk menutupi nomor target. Jika tidak ada, maka kembalilah ke tingkat rekursi sebelumnya.
  4. Jika ada cara untuk menutupi nomor target, pilih cara pertama dan panggil seluruh prosedur secara rekursif lagi, dengan pasangan yang baru saja dipilih menambah ke daftar pasangan yang dipilih.
  5. Ketika itu kembali, cari cara berikutnya untuk menutupi nomor target dengan pasangan, tanpa tumpang tindih dengan pasangan yang dipilih sebelumnya. Jika Anda menemukan satu, pilih dan ulangi lagi prosedur panggilan berikutnya.
  6. Lanjutkan langkah 4 dan 5 hingga tidak ada lagi cara untuk menutupi nomor target. Periksa seluruh daftar pasangan. Ketika tidak ada pilihan yang lebih benar, kembali ke level rekursi sebelumnya.

Cara untuk memvisualisasikan algoritma ini adalah dengan pohon yang jalurnya adalah urutan pasangan yang tidak tumpang tindih. Tingkat pertama pohon berisi semua pasangan yang berisi 0. Untuk contoh di atas, pohonnya adalah

           Akar
             |
     ----------------
     | | |
   (0,1) (0,2) (0,3)
     | | |
   (2,3) (1,3) (1,2)

Dalam contoh ini semua jalur melalui pohon benar-benar memberikan koleksi yang benar, tetapi misalnya jika kita meninggalkan pasangan (1,2) maka jalur paling kanan hanya akan memiliki satu simpul dan akan sesuai dengan pencarian di langkah 3 gagal.

Algoritme pencarian tipe ini dapat dikembangkan untuk banyak masalah yang sama dalam penghitungan semua objek dari tipe tertentu.


Disarankan bahwa mungkin OP berarti bahwa semua pasangan berada di input, bukan hanya satu set dari mereka seperti yang dikatakan dalam pertanyaan. Dalam hal ini algoritma lebih mudah karena tidak perlu lagi memeriksa pasangan mana yang diperbolehkan. Bahkan tidak perlu untuk menghasilkan set semua pasangan; pseudocode berikut akan melakukan apa yang diminta OP. Di sini adalah nomor input, "daftar" dimulai sebagai daftar kosong, dan "tertutup" adalah array dengan panjang diinisialisasi ke 0. Ini bisa dibuat agak lebih efisien tetapi itu bukan tujuan langsung saya.nnn

sub cover {
  i = 0;
  while ( (i < n) && (covered[i] == 1 )) {
   i++;
  }
  if ( i == n ) { print list; return;}
  covered[i] = 1;
  for ( j = 0; j < n; j++ ) {
    if ( covered[j] == 0 ) {
      covered[j] = 1;
      push list, [i,j];
      cover();
      pop list;
      covered[j] = 0;
    }
  }
  covered[i] = 0;
}
Carl Mummert
sumber
Ini seharusnya bekerja, tetapi mungkin itu bukan cara yang paling efisien untuk melakukannya.
Joe
2
Pada akhirnya, intinya adalah entah bagaimana untuk menyebutkan jalan pohon itu. Jika jumlah pasangan dalam daftar input jauh lebih kecil dari jumlah pasangan yang mungkin, algoritma semacam ini akan sangat efisien, terutama jika beberapa tabel hash digunakan untuk membantu mengingat angka-angka mana yang telah dicakup pada setiap langkah, sehingga ini dapat dipertanyakan dalam waktu yang konstan.
Carl Mummert
Jika daftar menggunakan pointer, maka Links Tari Knuth layak untuk dilihat. Ketika Anda kembali dari panggilan rekursif dan harus mengembalikan keadaan daftar sebelumnya.
uli
10

Sn[0,n)Sn+2Snn

def pairs(n):
    if (n%2==1 or n<2):
        print("no solution")
        return
    if (n==2):
        yield(  [[0,1]]  )
    else:
        Sn_2 = pairs(n-2) 
        for s in Sn_2:
            yield( s + [[n-2,n-1]] )
            for i in range(n/2-1):
                sn = list(s)
                sn.remove(s[i])
                yield( sn + [ [s[i][0], n-2] , [s[i][1], n-1] ] )
                yield( sn + [ [s[i][1], n-2] , [s[i][0], n-1] ] )

Anda dapat membuat daftar semua pasangan dengan menelepon

for x in pairs(6):
   print(x)
mitchus
sumber
6

Pembaruan : jawaban saya sebelumnya berkaitan dengan grafik bipartit, yang tidak ditanyakan oleh OP. Saya meninggalkannya untuk saat ini, sebagai info terkait. tetapi informasi yang lebih relevan berkaitan dengan pencocokan sempurna dalam grafik non-bipartit.

Dalam hal ini, ada survei yang bagus dari Propp yang menguraikan kemajuan (hingga 1999). Beberapa gagasan dalam artikel itu, dan tautan terkait, mungkin terbukti bermanfaat. TL; DR adalah - itu rumit :)

--- Mulai dari jawaban lama

Perhatikan bahwa yang Anda minta lakukan adalah menghitung semua kemungkinan pencocokan sempurna pada grafik bipartit. Ada banyak algoritma yang berbeda untuk melakukan ini, dan khususnya yang lebih baru adalah dari ISAAC 2001 .

Ide dasarnya adalah menemukan satu pencocokan sempurna dengan menggunakan aliran jaringan, dan kemudian berulang kali memodifikasi ini dengan menggunakan siklus bolak-balik (lihat bab algoritma buku teks tentang aliran jaringan untuk informasi lebih lanjut).

Suresh
sumber
Grafik bipartit terdiri dari dua set dengan label yang diberikan [0, n), dan ada keunggulan (i, j) jika dan hanya jika (i! = J)
Joe
Saya tidak berpikir Anda perlu meletakkan node untuk pasangan, kita bisa memperlakukannya sebagai ujung. Dengan kata lain kita memiliki grafik lengkapnKn
2
permanen menghitung jawabannya. tetapi OP ingin menyebutkannya
Suresh
semuanya adalah isomorfik karena struktur grafik sehingga berpikir tentang menerapkan permutasi mungkin merupakan ide yang baik (tetapi masalahnya adalah itu akan membuat duplikat).
Kaveh
4

Setiap pasangan yang Anda pilih menghilangkan dua baris yang tidak dapat Anda pilih lagi. Ide ini dapat digunakan untuk mengatur algoritma rekursif (dalam Scala):

def combine(pairs : Seq[(Int,Int)]) : Seq[Seq[(Int, Int)]] = pairs match {
  case Seq() => Seq()
  case Seq(p) => Seq(Seq(p))
  case _ => {
    val combinations = pairs map { case (a,b) => {
      val others = combine(pairs filter { case (c,d) =>
        a != c && a != d && b != c && b != d
      })

      others map { s => ((a,b) +: s) }
    }}

    combinations.flatten map { _.sorted } distinct
  }
}

Ini tentunya dapat diekspresikan dengan cara yang lebih efisien. Secara khusus, gagasan tidak harus mempertimbangkan seluruh baris untuk kombinasi tidak digunakan oleh panggilan ke filter.

Raphael
sumber
Tidakkah ini juga mengembalikan kombinasi yang tidak menyertakan setiap angka, tetapi yang tidak dapat diperpanjang karena tidak ada pasangan dalam urutan asli yang dapat memperpanjang mereka? Jika demikian, kombinasi tersebut perlu disaring.
Carl Mummert
n2N
(0,1)n=4
Iya nih. Tapi seperti yang saya katakan, jawaban saya berkaitan dengan skenario yang diusulkan OP, yaitu input tidak sewenang-wenang.
Raphael
Ketika saya membaca pertanyaan awal, ini tentang serangkaian pasangan yang berubah-ubah, OP tidak pernah mengatakan bahwa semua pasangan adalah mungkin. Tapi saya setuju OP bisa lebih jelas tentang itu.
Carl Mummert
4

Meskipun sudah ada banyak jawaban bagus untuk pertanyaan itu, saya pikir akan lebih baik untuk menunjukkan trik dasar, umum, di belakang mereka.

Jauh lebih mudah untuk menghasilkan kombinasi unik jika Anda dapat memiliki urutan total elemen yang akan digabungkan . Dengan cara ini, keunikan dijamin jika kami hanya mengizinkan kombinasi yang diurutkan. Tidak sulit untuk menghasilkan kombinasi yang diurutkan - cukup lakukan pencarian enumerasi brute force yang biasa, tetapi pada setiap langkah hanya pilih elemen yang lebih besar dari yang sudah diambil pada setiap langkah.

Komplikasi ekstra dalam masalah khusus ini adalah keinginan untuk mendapatkan hanya kombinasi panjang n / 2 (panjang maksimal). Ini tidak sulit dilakukan jika kita memutuskan strategi penyortiran yang bagus. Misalnya, seperti yang ditunjukkan dalam jawaban Carl Mummet, jika kita mempertimbangkan jenis leksikografis, (top-down, kiri-kanan dalam diagram dalam pertanyaan), kita memperoleh strategi untuk selalu mengambil elemen berikutnya sehingga digit pertamanya adalah nomor terkecil masih belum digunakan.

Kami juga dapat memperluas strategi ini jika kami ingin menghasilkan urutan panjang lainnya. Ingatlah bahwa setiap kali kita memilih elemen berikutnya yang nomor pertamanya bukan yang terkecil yang tersedia, kita mengesampingkan satu atau lebih barisan elemen agar tidak muncul pada urutan berikutnya, sehingga panjang maksimum praputasi akan berkurang.

hugomg
sumber
3

(n2)[n]={1,,n}[n]nKnn

[n]Perm(Kn)

#P-complete Knn!2n2

[n]

Kaveh
sumber