如何在另一个上应用一个有重复值的排列组合？

Question

考虑一下这个算法。

apply(src, perm) {
    result = []

    for (i; i < perm.length; i++) {
        result.push(src[perm[i]);
    }

    return result;
}

通过传递一个 src = [0,1,2,3] 和 perm = [3,0,1,2] 我们得到，在每次迭代中。

result -> 3
result -> 3 0
result -> 3 0 1
result -> 3 0 1 2

如果我们调用 apply 结果 apply(result, perm)，我们得到。

result -> 2 
result -> 2 3
result -> 2 3 0
result -> 2 3 0 1

以此类推。需要注意的是，如果我们执行这个操作，数组长度的倍数就会变成原始状态，但我需要在存在重复值的情况下执行这个操作，每个重复值都代表我的程序中的同一个元素。

但是，当存在重复的值时，我需要执行这个操作，每个重复的值将代表我的程序中的同一个元素。例如，我减少了数组中的元素数量。

- applying the perm (2 0 [1 1]) in src (0 [1 1] 2) should result in (2 0 [1 1]);
- applying the perm (2 0 [1 1]) in src (2 0 [1 1]) should result in (1] 0 2 [1);
- applying the perm (2 0 [1 1]) in src (1] 0 2 [1) should result in ([1 1] 0 2);
- ...

我减少了数组中的元素数量，以便更好地举例，但实际上，输入的长度为 12 (0 1 1 2 3 3 4 5 5 6 7 7). 此外，是不是只是循环旋转，如果perm不同，我想结果也会不同。另外，总是重复的值将只为 odd 和 even 数字是单数。

我试图写一个函数，试图检查一些东西，如当前的值是奇数还是偶数，如果奇数推下一个。

function apply(src, perm){
    res = [];
    last = 0;
    for (i = 0; i < perm.length; i++){
        if (src[perm[i]] % 2 === 0 && src[perm[i]] !== last){
            res.push(src[perm[i]]);
            last = src[perm[i]];
        } else if (src[perm[i]] % 2 === 0 && src[perm[i]] === last) {
            res.push(src[perm[i] + 1]);
            last = src[perm[i] + 1];
        } else {
            if (src[perm[i] + 1] !== undefined){ //out of bounds
                res.push(src[perm[i] + 1]);
                last = src[perm[i] + 1];
            }
        }
    }
    return res;
}

这里有一些输入和输出的例子。

base formula (no repetitions): result[i] = src[perm[i]]

Example 1:
src:    [4 1 1 2 5 5 0 3 3 6 7 7];
perm:   [4 1 1 6 3 3 0 5 5 2 7 7];
result: [0 1 1 6 5 5 4 3 3 2 7 7];

Example 2:
src:    [6 1 1 0 3 3 4 5 5 2 7 7];
perm:   [2 1 1 6 3 3 4 5 5 0 7 7];
result: [0 1 1 2 3 3 4 5 5 6 7 7];

Example 3:
src:    [0 1 1 2 3 3 6 5 5 4 7 7];
perm:   [2 3 3 4 5 5 6 7 7 0 1 1];
result: [2 3 3 6 5 5 4 7 7 0 1 1];

Example 4:
src:    [2 1 1 6 5 5 4 3 3 0 7 7];
perm:   [1 1 2 3 3 4 5 5 6 7 7 0];
result: [1 1 6 5 5 4 5 5 0 7 7 2];

Example 5:
src:    [6 7 7 0 1 1 4 5 5 2 3 3];
perm:   [3 3 4 5 5 6 7 7 0 1 1 2];
result: [1 1 4 5 5 2 3 3 6 7 7 0];

总之，这并不奏效。希望问题能说清楚，如果不清楚，欢迎提出任何问题。先谢谢你了。

Answer 1

这是有意义的。

perm (2 0 [1 1]) in src (0 [1 1] 2) result is (2 0 [1 1])

但从现在开始，就没有意义了。

perm (2 0 [1 1]) in src (2 0 [1 1]) result is (1] 0 2 [1)

让我们来看看: 首先你把元素 2 = [1 1]或 1，那么元素 0 = 2，那么元素 [1 1] = 0或 0, 0. 结果永远不会是 [1 0 2 1]

所以我相信你需要的是 perm 只有索引而没有重复。

perm (2 0 1) in src (0 [1 1] 2) result is (2 0 [1 1])
perm (2 0 1) in src (2 0 [1 1]) result is ([1 1] 2 0)
perm (2 0 1) in src ([1 1] 2 0) result is (0 [1 1] 2)

这也给了你循环属性。

假设这回答了你的问题，你需要首先删除重复的索引，然后在构造结果时，读取重复的索引。

更新：如果你的perm有重复，也要在运行algorythm之前删除这些重复。

function removeDuplicates(arr) { // Assumes duplicates are in order
  var result = [], prev = null;
  for (var el of arr) {
    if (el != prev) result.push(el);
    prev = el;
  }
  return result;
}

function apply(src, perm) {
  var result = [], prev = null;
  var src2 = removeDuplicates(src);
  for (var i of perm) {
    if (i != prev) { // Ignore duplicates
      var el = src2[i];
      result.push(el);
      if (el % 2 != 0) result.push(el); // duplicate odds
    }
    prev = i;
  }
  console.log(`src = [${src}] perm = [${perm}] result = [${result}]`);
}

apply([0, 1, 1, 2], [2, 0, 1]);
apply([2, 0, 1, 1], [2, 0, 1]);
apply([1, 1, 2, 0], [2, 0, 1]);

apply([4, 1, 1, 2, 5, 5, 0, 3, 3, 6, 7, 7], [4, 1, 1, 6, 3, 3, 0, 5, 5, 2, 7, 7]);
apply([6, 1, 1, 0, 3, 3, 4, 5, 5, 2, 7, 7], [2, 1, 1, 6, 3, 3, 4, 5, 5, 0, 7, 7]);
apply([0, 1, 1, 2, 3, 3, 6, 5, 5, 4, 7, 7], [2, 3, 3, 4, 5, 5, 6, 7, 7, 0, 1, 1]);
apply([2, 1, 1, 6, 5, 5, 4, 3, 3, 0, 7, 7], [1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 0]);
apply([6, 7, 7, 0, 1, 1, 4, 5, 5, 2, 3, 3], [3, 3, 4, 5, 5, 6, 7, 7, 0, 1, 1, 2]);