Mencari urutan integer

Saya memiliki masalah pencarian yang cukup rumit yang berhasil saya kurangi menjadi uraian berikut. Saya sudah googling tetapi belum bisa menemukan algoritma yang cocok dengan masalah saya. Khususnya kebutuhan untuk melewatkan bilangan bulat sewenang-wenang. Mungkin seseorang di sini bisa mengarahkan saya ke sesuatu?

Ambil urutan bilangan bulat A, misalnya (1 2 3 4)

Ambil berbagai urutan bilangan bulat dan uji apakah ada yang cocok dengan A sehingga.

1. A berisi semua bilangan bulat dalam urutan yang diuji
2. Urutan bilangan bulat dalam urutan yang diuji sama dalam A
3. Kami tidak peduli tentang bilangan bulat apa pun di A yang tidak dalam urutan pengujian
4. Kami ingin semua urutan uji yang cocok, bukan hanya yang pertama.

Sebuah contoh

A = (1 2 3 4)
B = (1 3)
C = (1 3 4)
D = (3 1)
E = (1 2 5)

B cocok dengan A

C cocok A

D tidak cocok dengan A karena pemesanannya berbeda

E tidak cocok dengan A karena mengandung bilangan bulat tidak dalam A

Saya harap penjelasan ini cukup jelas. Yang terbaik yang berhasil saya lakukan adalah membuat pohon dari urutan pengujian dan beralih ke A. Kebutuhan untuk dapat melewati bilangan bulat mengarah ke banyak jalur pencarian yang tidak berhasil.

Terima kasih

Membaca beberapa saran saya merasa saya harus mengklarifikasi beberapa poin yang saya tinggalkan terlalu kabur.

1. Angka berulang diperbolehkan, pada kenyataannya ini cukup penting karena memungkinkan urutan uji tunggal untuk mencocokkan A adalah beberapa cara

   A = (1234356), B = (236), kecocokan bisa berupa -23 --- 6 atau -2--3-6

2. Saya berharap akan ada jumlah yang sangat besar dari urutan pengujian, dalam ribuan setidaknya dan urutan A akan cenderung memiliki panjang maksimal mungkin 20. Dengan demikian hanya mencoba untuk mencocokkan setiap urutan pengujian satu per satu dengan iterasi menjadi sangat tidak efisien.

Maaf jika ini tidak jelas.

Hmm, saya bisa memikirkan dua algoritma yang mungkin: Pemindaian linear melalui urutan A , atau membangun kamus dengan pencarian indeks waktu-konstan.

Jika Anda menguji banyak kemungkinan berikutnya B terhadap urutan A yang lebih besar , saya sarankan Anda menggunakan varian dengan kamus.

Pemindaian Linier

Deskripsi

Kami menjaga kursor untuk urutan A . Kemudian kami mengulangi semua item dalam B berikutnya . Untuk setiap item, kami menggerakkan kursor maju dalam A sampai kami menemukan item yang cocok. Jika tidak ada item yang cocok ditemukan, maka B bukan yang berikutnya.

Ini selalu berjalan di O (seq.size) .

Kodesemu

Gaya imperatif:

def subsequence? seq, subseq:
  i = 0
  for item in subseq:
    i++ while i < seq.size and item != seq[i]
    return false if i == seq.size
  return true

Gaya fungsional:

let rec subsequence? = function
| _ [] -> true
| [] _ -> false
| cursor::seq item::subseq ->
  if   cursor = item
  then subsequence? seq subseq
  else subsequence? seq item::subseq

Contoh implementasi (Perl):

use strict; use warnings; use signatures; use Test::More;

sub is_subsequence_i ($seq, $subseq) {
  my $i = 0;
  for my $item (@$subseq) {
    $i++ while $i < @$seq and $item != $seq->[$i];
    return 0 if $i == @$seq;
  }
  return 1;
}

sub is_subsequence_f ($seq, $subseq) {
  return 1 if @$subseq == 0;
  return 0 if @$seq == 0;
  my ($cursor, @seq) = @$seq;
  my ($item, @subseq) = @$subseq;
  return is_subsequence_f(\@seq, $cursor == $item ? \@subseq : $subseq);
}

my $A = [1, 2, 3, 4];
my $B = [1, 3];
my $C = [1, 3, 4];
my $D = [3, 1];
my $E = [1, 2, 5];

for my $is_subsequence (\&is_subsequence_i, \&is_subsequence_f) {
  ok $is_subsequence->($A, $B), 'B in A';
  ok $is_subsequence->($A, $C), 'C in A';
  ok ! $is_subsequence->($A, $D), 'D not in A';
  ok ! $is_subsequence->($A, $E), 'E not in A';
  ok $is_subsequence->([1, 2, 3, 4, 3, 5, 6], [2, 3, 6]), 'multiple nums';
}

done_testing;

Pencarian kamus

Deskripsi

Kami memetakan item dari urutan A ke indeks mereka. Kemudian kami mencari indeks yang sesuai untuk setiap item dalam B , melewati indeks yang kecil, dan memilih indeks sekecil mungkin sebagai batas bawah. Ketika tidak ada indeks yang ditemukan, maka B bukanlah sebuah urutan.

Berjalan dalam sesuatu seperti O (subseq.size · k) , di mana k menjelaskan berapa banyak angka duplikat di dalamnya seq. Ditambah overhead O (seq.size)

Keuntungan dari solusi ini adalah bahwa keputusan negatif dapat dicapai lebih cepat (turun ke waktu konstan), setelah Anda membayar biaya overhead untuk membangun tabel pencarian.

Kodesemu:

Gaya imperatif:

# preparing the lookup table
dict = {}
for i, x in seq:
  if exists dict[x]:
    dict[x].append(i)
  else:
    dict[x] = [i]

def subsequence? subseq:
  min_index = -1
  for x in subseq:
    if indices = dict[x]:
      suitable_indices = indices.filter(_ > min_index)
      return false if suitable_indices.empty?
      min_index = suitable_indices[0]
    else:
      return false
  return true

Gaya fungsional:

let subsequence? subseq =
  let rec subseq-loop = function
  | [] _ -> true
  | x::subseq min-index ->
    match (map (filter (_ > min-index)) data[x])
    | None -> false
    | Some([]) -> false
    | Some(new-min::_) -> subseq-loop subseq new-min
  in
    subseq-loop subseq -1

Contoh implementasi (Perl):

use strict; use warnings; use signatures; use Test::More;

sub build_dict ($seq) {
  my %dict;
  while (my ($i, $x) = each @$seq) {
    push @{ $dict{$x} }, $i;
  }
  return \%dict;
}

sub is_subsequence_i ($seq, $subseq) {
  my $min_index = -1;
  my $dict = build_dict($seq);
  for my $x (@$subseq) {
    my $indices = $dict->{$x} or return 0;
    ($min_index) = grep { $_ > $min_index } @$indices or return 0;
  }
  return 1;
}

sub is_subsequence_f ($seq, $subseq) {
  my $dict = build_dict($seq);
  use feature 'current_sub';
  return sub ($subseq, $min_index) {
    return 1 if @$subseq == 0;
    my ($x, @subseq) = @$subseq;
    my ($new_min) = grep { $_ > $min_index } @{ $dict->{$x} // [] } or return 0;
    __SUB__->(\@subseq, $new_min);
  }->($subseq, -1);
}

my $A = [1, 2, 3, 4];
my $B = [1, 3];
my $C = [1, 3, 4];
my $D = [3, 1];
my $E = [1, 2, 5];

for my $is_subsequence (\&is_subsequence_i, \&is_subsequence_f) {
  ok $is_subsequence->($A, $B), 'B in A';
  ok $is_subsequence->($A, $C), 'C in A';
  ok ! $is_subsequence->($A, $D), 'D not in A';
  ok ! $is_subsequence->($A, $E), 'E not in A';
  ok $is_subsequence->([1, 2, 3, 4, 3, 5, 6], [2, 3, 6]), 'multiple nums';
}

done_testing;

Varian Pencarian Kamus: Pengkodean sebagai Mesin Status Hingga

Deskripsi

Kami selanjutnya dapat mengurangi kompleksitas algoritme hingga O (subseq.size) jika kami menukar lebih banyak memori. Alih-alih memetakan elemen ke indeks mereka, kami membuat grafik di mana setiap node mewakili elemen di indeksnya. Tepi-tepinya menunjukkan kemungkinan transisi, misalnya urutan a, b, amemiliki tepian a@1 → b@2, a@1 → a@3, b@2 → a@3. Grafik ini setara dengan mesin keadaan terbatas.

Selama pencarian, kami mempertahankan kursor yang awalnya merupakan simpul pertama dari pohon. Kami kemudian berjalan tepi untuk setiap elemen dalam sublist B . Jika tidak ada tepi seperti itu, maka B tidak ada sublist. Jika setelah semua elemen kursor berisi simpul yang valid, maka B adalah sublist.

Kodesemu

Gaya imperatif:

# preparing the graph
graph = {}
for x in seq.reverse:
  next_graph = graph.clone
  next_graph[x] = graph
  graph = next_graph

def subseq? subseq:
  cursor = graph
  for x in subseq:
    cursor = graph[x]
    return false if graph == null
  return true

Gaya fungsional:

let subseq? subseq =
  let rec subseq-loop = function
  | [] _ -> true
  | x::subseq graph -> match (graph[x])
    | None -> false
    | Some(next-graph) -> subseq-loop subseq next-graph
  in
    subseq-loop subseq graph

Contoh implementasi (Perl):

use strict; use warnings; use signatures; use Test::More;

sub build_graph ($seq) {
  my $graph = {};
  for (reverse @$seq) {
    $graph = { %$graph, $_ => $graph };
  }
  return $graph;
}

sub is_subsequence_i ($seq, $subseq) {
  my $cursor = build_graph($seq);
  for my $x (@$subseq) {
    $cursor = $cursor->{$x} or return 0;
  }
  return 1;
}

sub is_subsequence_f ($seq, $subseq) {
  my $graph = build_graph($seq);
  use feature 'current_sub';
  return sub ($subseq, $graph) {
    return 1 if @$subseq == 0;
    my ($x, @subseq) = @$subseq;
    my $next_graph = $graph->{$x} or return 0;
    __SUB__->(\@subseq, $next_graph);
  }->($subseq, $graph);
}

my $A = [1, 2, 3, 4];
my $B = [1, 3];
my $C = [1, 3, 4];
my $D = [3, 1];
my $E = [1, 2, 5];

for my $is_subsequence (\&is_subsequence_i, \&is_subsequence_f) {
  ok $is_subsequence->($A, $B), 'B in A';
  ok $is_subsequence->($A, $C), 'C in A';
  ok ! $is_subsequence->($A, $D), 'D not in A';
  ok ! $is_subsequence->($A, $E), 'E not in A';
  ok $is_subsequence->([1, 2, 3, 4, 3, 5, 6], [2, 3, 6]), 'multiple nums';
}

done_testing;

Berikut ini adalah pendekatan praktis yang menghindari "kerja keras" menerapkan algoritma Anda sendiri, dan juga menghindari "menciptakan kembali roda": memanfaatkan mesin ekspresi reguler untuk masalah tersebut.

Masukkan semua angka A ke dalam string, dan semua angka B ke dalam string yang dipisahkan oleh ekspresi reguler (.*). Tambahkan ^karakter di awal dan $di akhir. Kemudian biarkan mesin ekspresi reguler favorit Anda mencari semua kecocokan. Misalnya kapan

A = (1234356), B = (236)

buat reg exp untuk B like ^(.*)2(.*)3(.*)6(.*)$. Sekarang jalankan pencarian regexp global. Untuk mengetahui posisi mana dalam A yang sesuai dengan Anda, cukup periksa panjang dari 3 kiriman pertama.

Jika rentang bilangan bulat Anda meninggalkan 0 hingga 9, Anda dapat mempertimbangkan untuk menyandikannya dengan huruf tunggal terlebih dahulu untuk membuat ini berfungsi, atau Anda harus menyesuaikan ide menggunakan karakter pemisahan.

Tentu saja, kecepatan pendekatan itu akan sangat bergantung pada kecepatan mesin reg exp yang Anda gunakan, tetapi ada mesin yang sangat dioptimalkan yang tersedia, dan saya kira akan sulit untuk menerapkan algoritma yang lebih cepat "di luar kotak" .

Algoritma ini harus cukup efisien jika mendapatkan panjang dan mengulangi urutannya efisien.

1. Bandingkan panjang kedua urutan. Simpan lebih lama sequencedan lebih pendeksubsequence
2. Mulai dari awal urutan dan putaran sampai akhir sequence.
   1. Apakah angka pada posisi saat ini sequencesama dengan angka pada posisi saat inisubsequence
   2. Jika ya, pindahkan kedua posisi satu lebih jauh
   3. Jika tidak, gerakkan hanya posisi sequencesatu lebih jauh
3. Apakah posisi subsequencepada akhirsequence
4. Jika ya, dua urutan cocok
5. Jika tidak, kedua urutan tidak cocok