Jak mogę wygenerować wszystkie możliwe posortowane tablice z alternatywnych elementów dwóch posortowanych tablic?

Question

Ostatnio spotkałem się z tym pytaniem w wywiadzie. Tak naprawdę nie byłem w stanie wymyślić odpowiedzi na to pytanie. Zacząłem od, weź pierwszy element z pierwszej tablicy, a następnie znajdź ile elementów jest większe od tego elementu w drugiej tablicy. Ale wtedy, mam na myśli, nie wiem, nie mogłem naprawdę stworzyć rozwiązania. Problem jest następujący:

Biorąc pod uwagę dwie posortowane tablice A i B, generuj wszystkie możliwe macierze tak, że pierwszy element jest pobierany z A, a następnie z B, a następnie z A i tak dalej, aż do wyczerpania macierzy. Generowane tablice powinny kończyć element z B.

Eg: 
A = {10, 15, 25} 
B = {1, 5, 20, 30} 

The resulting arrays are: 
    10 20 
    10 20 25 30 
    10 30 
    15 20 
    15 20 25 30 
    15 30 
    25 30 

ja nie szukam kodu, tylko algo/pseduo Kod zrobi dobrze. Dzięki!

Answer 1

Jak się za pomocą skierowanego wykres z wyszukiwania BFS ścieżek.

1. Utwórz directed graph, gdzie krawędź skierowana jest tworzona z elementu w tablicy A do każdego elementu w tablicy B, jeśli ten element w B jest większy. I vice werset. Kierowana krawędź jest tworzona z elementu w tablicy B do każdego elementu w tablicy A, jeśli ten element w A jest większy.
2. Wybierz element z A
3. Następnie użyj wyszukiwania BFS, aby wygenerować wszystkie możliwe ścieżki.
4. każdym razem, gdy ścieżka zawiera element z B dodać, że sub-path do listy rozwiązań ścieżek
5. zatrzyma się, gdy wszystkie elementy zostały wykorzystane jako poszukiwanie klucza

Aktualizacja

za sugestią przez @MiljenMikic można wykorzystać fakt, że tablice są klasyfikowane według przyspieszenia Krok 1. nie musisz szukać wszystkie elementy w drugiej tablicy znaleźć większe niż elementy. Po prostu śledź ostatnio znaleziony i przesuń wskaźnik do przodu podczas wyszukiwania.

Answer 2

rozwiązanie BFS że @dpmcmlxxvi proponowany jest interesująca. Ponadto sugerowałbym wariant rekursywny. Kilka podstawowych punktów:

• jednym z argumentów wejściowych funkcji rekursywnej powinna być zmienna binarna, która wskaże, czy należy dodać element z A, czy z B; można przełączać tę wartość w kolejnych wywołań rekurencyjnych

• tablice są klasyfikowane - wykorzystać te informacje! Kiedy zobaczysz posortowane tablice, zawsze myślę o binarnego wyszukiwania - w tym przypadku należy rekurencyjnie przechodzić Ostatni dodany element, a następnie w drugiej tablicy, przeszukiwanie binarne dla pierwszego elementu, który jest większy niż ten ostatni element

• jeżeli ostatnia dodana elementem była od B, dodać aktualną tablicę roboczą do otrzymanej listy

Answer 3

rekurencyjne proste rozwiązanie oparte na technologii Java może być tak

public static void main(String[] args) { 

    int[] A = {10, 15, 25}; 
    int[] B = {1, 5, 20, 30}; 

    Stack<Integer> st = new Stack<>(); 

    for (int i = 0; i < A.length; i++) { 
     st.push(A[i]); 
     generateArrays(A, B, i, 0, st, false); 
     st.clear(); 
    } 
} 

static void generateArrays(int ar1[], int ar2[], int index_of_a, int index_of_b, Stack<Integer> st, boolean first) { 
    if (index_of_a >= ar1.length || index_of_b >= ar2.length) { 
     st.pop(); 
     return; 
    } 

    // take from second if available 
    if (!first) { 
     for (int j = index_of_b; j < ar2.length; j++) { 
      if (ar1[index_of_a] < ar2[j]) { 
       st.push(ar2[j]); 
       System.out.println(st); 
       generateArrays(ar1, ar2, index_of_a + 1, j, st, true); 
      } 
     } 
    } 

    // take from first if available 
    else if (first) { 
     for (int i = index_of_a; i < ar1.length; i++) { 
      if (ar1[i] > ar2[index_of_b]) { 
       st.push(ar1[i]); 
       generateArrays(ar1, ar2, i, index_of_a + 1, st, false); 
      } 
     } 
    } 

    st.pop(); 
}