C匹配算法(使用递归+排列)

Question

我发现很多关于我的作业主题的研究都接近我想要的，但不完全是。似乎许多作业都被迫找到字符串的排列，这与方法类似。我是递归的新手，因此很难跟踪代码。我在另一篇文章中找到了这个片段:

void swap(char* str, int i, int j)
{
    char temp = str[i];
    str[i] = str[j];
    str[j] = temp;
}

void permute(char *string, int start, int end)
{
    if(start == end)
   {
        printf("%s\n", string);
        return;
    }

    permute(string, start + 1, end);
    int i;
    for(i = start + 1; i < end; i++)
    {
        if(string[start] == string[i])
            continue;
        swap(string, start, i);
        permute(string, start + 1, end);
        swap(string, start, i);
    }
}

从那里我可以看出基本情况是字符串的长度与 i 的索引相同。然而，对于我的任务，我们要做一些稍微不同的事情。我们被要求在可能的情侣之间扮演“媒人”的角色。我们有相同数量的男性和女性，每个人都有一个“匹配性”衡量标准。我们的目标是最大化这个匹配度数。因此，如果是 3 男 * 3 女(总是完美的情侣)，我会:

 {[M1, W1], {[M1, W1], {[M1, W2],
  [M2, W2],  [M2, W3],  [M2, W1],
  [M3, W3]}  [M3, W2]}  [M3, W3]}
  ....
  // Match #(n)! or in this case 6 (3*2*1)

;

等等。我知道由此产生的排列数将是 (n)!其中 n 是对数。因此，10 名男性和 10 名女性将是 (10)!解决方案。考虑到这一切，我发现的这段代码是否与我应该寻找的相似，或者是否需要修改？我相信 must be modified 因为这是排列一个线性数组，而我的情况可以是排列两个单独的数组。

大家怎么看？

Answer 1

您不需要排列 2 个单独的数组 - 您只需要排列其中一个，并在匹配时保持另一个不变。这足以保证您检查所有可能的解决方案以匹配男性和女性。证明很简单，Men 只是女性的索引，而 women 数组的所有排列只是找到所有排序它们的方法 - 即为女性分配索引的所有可能性。

让我们看一个 3 男 3 女的简单例子:

data = [M1,M2,M3] [W1,W2,W3]
opt1: M1+W1, M2+W2, M3+W3
opt2: M1+W1, M2+W3, M3+W2
opt3: M1+W2, M2+W1, M3+W3
opt4: M1+W2, M2+W3, M3+W1
opt5: M1+W3, M2+W1, M3+W2
opt6: M1+W3, M2+W2, M3+W1

很容易看到这些都是可能的，我们只排列了女性数组([W1,W2,W3])，而男性数组保持原样。

---

编辑:
根据您已有的代码，可以执行以下操作:

int permute(int men[], int women[], int start, int end)
{
    if(start == end)
   {
        int i =0, sum = 0;
        for (i = 0; i < end; i++) sum += score(men[i],women[i]);
        return sum;
    }
    best = -INFINITY;
    best = max(permute(men, women, start + 1, end), best);
    int i;
    for(i = start + 1; i < end; i++)
    {
        if(women[start] == women[i])
            continue;
        swap(string, start, i);
        best = max(permute(men, women, start + 1, end), best);
        swap(women, start, i);
    }
    return best;
}

以上仅排列women，并在停止子句中检查分数(假设为 int)并返回在迭代中找到的“最佳”分数(假设最佳是此处最高的) .
我还假设你有一些函数 int score(int,int) 可以找到每场比赛的得分

注意:这是一个 c 风格的伪代码，它没有经过测试，可能有一些语法问题。