1

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

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）！解决方案。考虑到这一切，我发现的这段代码是否与我应该寻找的相似，还是需要修改？我相信必须修改，因为这是置换一个线性数组，我的情况可以是置换两个单独的数组。

你们有什么感想？

4

1 回答 1

1

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

让我们看一个简单的 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

很容易看出这些都是可能的，我们只置换了 women 数组 ( [W1,W2,W3]) 而 men 数组保持原样。

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

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, 并在 stop 子句中检查分数（假设为 int）并返回在迭代中找到的“最佳”分数（假设最佳是此处的最高分数）。
我还假设你有一些函数int score(int,int)可以找到每场比赛的得分

注意：这是一个 c 风格的伪代码，未经测试，可能存在一些语法问题。

于 2013-01-31T11:17:25.213 回答