Как рекурсивно выполнить метод грубой силы

Question

Я пытаюсь создать рекурсивный алгоритм, используя грубую силу.Предполагается, что этот алгоритм сравнивает целые числа и «редактирует расстояние», если сравниваемые целые числа не похожи.Пример: 3254 должно быть 2345. EditDistance здесь будет 2 [(3,2) (5,4)].

Мой код компилируется, но он не дает никакого вывода.Если бы кто-нибудь мог помочь мне решить проблему, это было бы очень благодарно.

public static int measureEditDistance(int[] rankings) {
    int editDistance = 0;
    int R = rankings.length;

    // You need to write this method.
    //   Add your logic here to compute the editDistance

    for (int m = 0; m < R; m++) {
        for (int i = m + 1; i < R; i++) {
            for (int j = i + 1; j < R; j++) {
                if (rankings[m] + rankings[i] + rankings[j] == 0) {
                    editDistance++;
                }
            }
        }
    }

    return editDistance;
}

Answer 1

Истинный метод грубой силы потребует от вас найти все перестановки данного числа.Итак, вот методы, чтобы сделать это (рекурсивно):

void swap(int[] arr, int x, int y) {
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}


void permute(int[] arr) {
    permute(arr, 0, arr.length - 1);
}


void permute(int[] arr, int i, int n) {
    int j;
    if (i == n)
        System.out.println(Arrays.toString(arr));
    else {
        for (j = i; j <= n; j++) {
            swap(arr, i, j);
            permute(arr, i + 1, n);
            swap(arr, i, j); // backtrack
        }
    }
}

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

int temp[] = {3, 2, 4, 5};

Итак, мы можем проверить.мы должны изменить код permute(int[]) на:

int permute(int[] arr, int[] rankings){
    int distancevar = 0;
    distance var = permute(arr,rankings,0,arr.length-1);
    return distancevar;

}

Тогда нам придется изменить тип возвращаемого значения permute(int[], int, int) на int, чтобы мы могли вернуть расстояние, которое мы нашли истинным.Это сделает код следующим образом:

int permute(int[] arr, int[] rankings, int i, int n) {
    int j;
    int ans = 0;
    bool isAns = false;
    if (i == n)
        System.out.println(Arrays.toString(arr));
    else {
        for (j = i; j <= n; j++) {
            swap(arr, i, j);
            isAns = check(arr, rankings);
            if(isAns){
                **here you would call your distance check on the two arrays, 
    which I am still unsure of what you actually are doing here**
                ans = *some distance calc*;
                return ans;
            }
            ans = permute(arr,rankings, i + 1, n);
            if (ans == 0){
                swap(arr, i, j); // backtrack
                isAns = check(arr, rankings);
                if(isAns){
                    **here you would call your distance check on the two arrays, 
        which I am still unsure of what you actually are doing here**
                    ans = *some distance calc*;
                    return ans;
                }
        }
    }
    return ans;
}

Теперь в вашей функции перестановки проверьте массив на соответствие вашему условию.

bool check(int[] arr, int[] ans)
    int same = 0
    for(int i = 0; i < temp.length; i++){
        if(temp[i] == ans[i])
            same++;
    if (same == 4)
        return true;
    return false;

Как только эти функции завершены, единственный код, который должен бытьв main будет выглядеть следующим образом:

int ans = permute(*your array to test*, *final array desired*);
System.out.println(ans);

Пояснение

Обратите внимание, как функция permute вызывает себя и возвращает ans, где ans = distance_value.Это значение затем передается обратно через ВСЕ вызовы функций.Это рекурсия.