Поиск пары в Go

Question

Здесь я пытаюсь сформировать расположение, которое содержит пары чисел, каждая пара которых m's разделена m элементами. например:

• для [0,2], расположение пар равно [2,0, 0,2], так что m = 2, поэтому число 2 разделено 2 элементами.
• для [0,1] = нет действительного расположения

Я до сих пор не могу понять шаблон или алгоритм для расположения, так как мне нужно найти расположение до [0, 1,2,3,4,5,6,7,8]. однако действительный порядок для этого списка [3,7,8,2,3,1,2,1,6,7,5,8,4,0,0,6,5,4], если делать это вручную.

В приведенных ниже кодах я мог только переставить числа в списке, получив сначала самое большое число в списке. Я хочу знать, как разделить пару по номеру пары (например, если пара равна 2, следовательно, номер разделения равен 2)

как я могу сделать разделение и шаблон для списка чисел?

    package main

    import "fmt"

    func MagicPairs(list []int) {
        //length := len(list) * 2
        magicPair := []int{}
        magicPair = append(list, list...)

        for i := 0; i <len(magicPair); i++{
            if len(magicPair) == 0 {
                //do nothing
            }else{  
                m := max(list)
                for p, x := range magicPair{
                    if magicPair[len(magicPair)-1] == m {   
                        magicPair = append([]int{m}, (magicPair)[:len(magicPair)-1]...)
                        fmt.Println(magicPair)
                        return
                    }
                    if x == m{
                        magicPair = append([]int{m}, append((magicPair)[:p], (magicPair)[p+1:]...)...)
                    }

                    previousPair := magicPair[x]
                    if x == previousPair{

                    }

                }
            }
        }
        fmt.Println("1", magicPair)
    }

    func max(list[] int) int{
        max := list[0]
        for _, value := range list{
            if value > max {
                max = value 
            }
        }
        return max
    }

    func main(){
        list := [] int {0,1,2,3,4,5,6,7,8}
        MagicPairs(list)

    }

Answer 1

Кажется, вы пытаетесь найти оптимальное решение, удваивая список источников, а затем перемешивая числа, многократно разбивая и объединяя массив.

Я думаю, что эта проблема поддается рекурсивному подходу. Создайте целевой массив с 2 * len(list) пустыми слотами. (Независимо от того, является ли слот пустым или нет, его нужно пометить специальным значением, например -1.) Затем рекурсивно попытаться вписать элементы исходного массива в целевой массив.

Давайте рассмотрим ваш пример{0, 1, 3}. Создайте целевой массив:

. . . . . .

Попробуйте все возможные зелья для 0. Первое -

0 0 . . . .

Теперь попробуйте соответствовать 1. Есть две возможности

0 0 . . . .
0 0 1 . 1 .

но это не будет соответствовать следующему элементу, 3. Вернитесь на один шаг назад:

0 0 . . . .
0 0 . 1 . 1

Здесь 3 тоже не вписываются. Мы исчерпали наш поиск этой позиции нулей, поэтому давайте возьмем следующую жизнеспособную позицию нулей:

. 0 0 . . .

Есть только один способ разместить одну:

. 0 0 . . .
. 0 0 1 . 1

Сейчасдавайте попробуем подобрать 3 и, бинго!, оно подходит:

. 0 0 . . .
. 0 0 1 . 1
3 0 0 1 3 1

Теперь вы можете остановить поиск или попытаться найти другие решения. В этом случае есть только одно решение, а именно отражение этого, но есть 300 способов разместить числа от 1 до 8, например, враг.

Этот подход в значительной степени грубая сила, но вНа практике, существует не так много правильных способов заполнения массива, поэтому неправильные пути обнаруживаются рано. Возможно, размещение первых чисел сначала даст лучшую производительность. Вы можете поиграть с этим и измерить его.

Вот программа, которая делает это. (Вероятно, это больше похоже на C, чем на Go. Не берите в голову.)

package main

import "fmt"

func fit_r(res[] int, a[] int, i int) int {
    n := len(a);

    if i == n {
        fmt.Printf("%v\n", res);
        return 1;
    } else {
        count := 0;
        m := a[i];

        for j := 0; j < 2*n - 1 - m; j++ {
            if res[j] == -1 && res[j + 1 + m] == -1 {
                // place values
                res[j] = m;
                res[j + 1 + m] = m;

                // test further values
                count += fit_r(res, a, i + 1);

                // clean up and remove values again
                res[j] = -1;
                res[j + 1 + m] = -1;
            }
        }        

        return count;
    }
}

func fit(a[] int) int {
    res := make([] int, 2 * len(a));

    for i := range res {
        res[i] = -1;
    }

    return fit_r(res, a, 0);
}

func main() {
    list := [] int {0, 1, 2, 3};
    n := fit(list);

    fmt.Println(n, "solutions");
}