JavaScript中具有重复元素的唯一排列

schl3ck

假设我们有元素0和1,它可以occour不止一次,像00 00 1100 00 11 1101 11(分成2组进行更好的可读性)。

我已经有一个生成所有唯一排列的函数:

class UniqueElement {
  constructor(value, occurrences) {
    this.value = value;
    this.occurrences = occurrences;
  }
}

function permUnique(elements) {
  let set = new Set(elements);
  let listunique = Array.from(set).map((i) => new UniqueElement(i, elements.filter((el) => el === i).length));
  let u = elements.length;
  return permUniqueHelper(listunique, "0".repeat(u).split("").map((i) => parseInt(i)), u - 1);
}
function* permUniqueHelper(listunique, result_list, d) {
  if (d < 0) {
    yield [...result_list];
  } else {
    for (const i of listunique) {
      if (i.occurrences > 0) {
        result_list[d] = i.value;
        i.occurrences--;
        for (const g of permUniqueHelper(listunique, result_list, d - 1)) yield g;
        i.occurrences++;
      }
    }
  }
}

// call like:
// permUnique([0,0,1,1])
console.log(Array.from(permUnique([0,0,1,1])).join('\n'));

从这里翻译成JavaScript:https : //stackoverflow.com/a/6285203/10362619

现在,我的意图是将这些生成的排列用作其他对象的索引。然后在代码中使用这些对象,这些对象的顺序无关紧要:

10 10
01 01

到底是一样的,还是

01 20 12
02 10 21
10 21 02
12 01 20
...

对于用碱012从起动00 11 22

它们被认为是相同的,因为相同的数字位于相同的位置。只需切换两个数字(例如0与1),您就会得到另一个。

同样,所有这些示例都被分成两组,以提高可读性。00 11 22含义与相同001122,其中每个数字都是输入数组中的单个元素。

创建排列后,是随后过滤元素的最快方法,还是可以在函数中实现此条件?

编辑:不需要它是置换数组的生成器函数

编辑2:为了更清楚让事情:我给第一个例子有模式abab,其中a可以是01b是相反的。第二个例子遵循模式abcabc,其中abc可以全部或者012(但不相同)。

贝吉

在不同排列之间具有相等条件后,我们需要为每个模式(相等类)建立规范形式然后,我们将尝试仅生成那些。

在你的情况,其中顺序1S,2S和3s没有问题,我们可以决定它们各自的第一出现一定的顺序123,而2不能出现不13并非没有2因此,图案是否为aabcbcaacbcbbbacac,...,或者ccbaba,我们要生成的唯一形式112323或模式是aaa/ bbb/时,ccc我们只生成111而不是222333

然后,我们可以编写遵循以下规则的规范形式的算法:

function patterns(values, len) {
    function* recurse(list, used, depth) {
        if (depth == len) {
            yield list.slice();
        } else {
            for (let j=0; j<used; j++) { // only put already used values at this position
                list[depth] = values[j];
                yield* recurse(list, used, depth+1);
            }
            if (used < values.length) { // or the single next unused value
                list[depth] = values[used];
                yield* recurse(list, used+1, depth+1); // which is counted as used here
            }
        }
    }
    return recurse([], 0, 0);
}

这只是从distinct生成一定长度的所有组合values,但是您可以在算法中使用相同的方法,根据一定数量的非唯一值生成排列。但是,它确实变得更加复杂:121如果我们只有122可用的值则无法实现规范形式,但212仍应生成模式我们需要调整规则,以使排序要求仅出现在相同次数的元素之间。因此,我们必须used为他们保留不同的数量。

function permutationPatterns(elements) {
    const len = elements.length;
    const unique = new Map(elements.map(el => [el, {value: el, occurrences: 0}]));
    let max = 0;
    for (const el of elements) {
        const o = unique.get(el);
        max = Math.max(max, ++o.occurrences);
    }
    const byOccurrences = Array.from({length: max+1}, () => ({elements: [], used: 0}));
    for (const o of unique.values()) {
        byOccurrences[o.occurrences].elements.push(o);
    }

    function* generate(list, depth) {
        if (depth == len) {
            yield list.slice();
        } else {
            for (const options of byOccurrences) {
                options.used++;
                for (const option of options.elements.slice(0, options.used)) {
                    if (option.occurrences == 0) continue;
                    option.occurrences--;
                    list[depth] = option.value;
                    yield* generate(list, depth+1);
                    option.occurrences++;
                }
                options.used--;
            }
        }
    }
    return generate([], 0);
}

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

TOP 榜单

热门标签

归档