Как найти все разделы мультимножества, где каждая часть имеет отдельные элементы?

Question

Допустим, у нас есть такой массив: myArray = [A, A, B, B, C, C, D, E]

Я хотел бы создать алгоритм, чтобы он нашел всекомбинации, которые составляют весь массив, где ни один из элементов не повторяется.

Примеры комбинаций:

[A, B, C, D, E] [A, B, C]
[A, B, C, D] [A, B, C, E]
[A, B, C] [A, B, C] [D, E]

Разъяснение: [A, B, C] [A, B, C] [D, E] и [A, B, C] [D, E] [A, B, C] - это одинаковые комбинации.Кроме того, порядок с подмножествами также не имеет значения.Например, [A,B,C] и [B,A,C] должны совпадать.До сих пор я не продвинулся дальше

var myArray = ["A", "A", "B", "B", "C", "C", "D", "E"]

console.log([...new Set(myArray)])

Но это совсем не помогает, оно просто возвращает один отдельный набор.Я не мог найти похожую проблему, опубликованную ранее, поэтому кто-нибудь может подсказать мне, как этого добиться?

Answer 1

Я получаю 315 комбинаций.Это правильно?:)

Вот рекурсия:

function distribute(e, i, _comb){
  // No more e's
  if (e[1] == 0)
    return [_comb];
  // We're beyond the combination
  if (i == -1)
    return [_comb.concat([e])];
  let result = [];
  for (let c=1; c<=Math.min(_comb[i][1], e[1]); c++){
    let comb = _comb.map(x => x.slice());

    if (c == comb[i][1]){
      comb[i][0] += e[0];

    } else {
      comb[i][1] -= c;
      comb.push([comb[i][0] + e[0], c]);
    }
    result = result.concat(distribute([e[0], e[1] - c], i - 1, comb));
  }
  let comb = _comb.map(x => x.slice());
  return result.concat(distribute(e, i - 1, comb));
}

function f(arr){
  function g(i){
    if (i == 0)
      return [[arr[0]]];
    const combs = g(i - 1);
    let result = [];
    for (let comb of combs)
      result = result.concat(
        distribute(arr[i], comb.length - 1, comb));
    return result;
  }
  return g(arr.length - 1);
}

function show(arr){
  const rs = f(arr);
  const set = new Set();

  for (let r of rs){
    const _r = JSON.stringify(r);
    if (set.has(_r))
      console.log('Duplicate: ' + _r);
    set.add(_r);
  }

  let str = '';
  for (let r of set)
    str += '\n' + r
  str += '\n\n';

  console.log(JSON.stringify(arr));
  console.log(set.size + ' combinations:');
  console.log(str);
}

show([['A', 2], ['B', 2], ['C', 2], ['D', 1], ['E', 1]]);

Answer 2

Реализован алгоритм с нуля, который:

• получает частоту букв,
• начинается с длины ключа и работает вниз до 1
• , в то время какКарта частот не пуста
  • добавить ключ к вспомогательному результату

const decrementKey = (o, k) => o[k]--;
const isEmpty = (o) => Object.keys(o).length === 0;
const removeKeys = (o) => Object.keys(o).forEach(k => { if (o[k] < 1) delete o[k]; });
const frequencyMap = (a) => a.reduce((r, v) => Object.assign(r, { [v] : (r[v] || 0) + 1 }), {});
const cloneMap = (o) => Object.keys(o).reduce((r, k) => Object.assign(r, { [k] : o[k] }), {});

let myArray = ["A", "A", "B", "B", "C", "C", "D", "E"];
let groups = solve(myArray);

console.log(groups.map(g => g.map(a => a.join('')).join(' | ')).join('\n'));

function solve(arr) {
  let freq = frequencyMap(arr), results = [];
  for (let max = Object.keys(freq).length; max > 1; max--) {
    let result = [], clone = cloneMap(freq);
    while (!isEmpty(clone)) {
      result.push(Object.keys(clone).reduce((res, key, index) => {
        if (index < max) {
          decrementKey(clone, key);
          res.push(key);
        }
        return res;
      }, []));
      removeKeys(clone);
    }
    if (result.length > 0) results.push(result);
  }
  return results;
}

.as-console-wrapper { top: 0; max-height: 100% !important; }

Answer 3

Вы могли бы сделать это, перечислив все возможные комбинации, а затем найдя перестановки для каждой комбинации, а затем отфильтровав элемент, чтобы убедиться, что они уникальны.Эту фильтрацию можно выполнить, вставив в набор.

Функция подмножества взята из @le_m ( Проверьте этот ответ ).

function* subsets(array, offset = 0) {
  while (offset < array.length) {
    let first = array[offset++];
    for (let subset of subsets(array, offset)) {
      subset.push(first);
      yield subset;
    }
  }
  yield [];
}

function* permutations(elements) {
  if (elements.length === 1) {
    yield elements;
  } else {
    let [first, ...rest] = elements;
    for (let perm of permutations(rest)) {
      for (let i = 0; i < elements.length; i++) {
        let start = perm.slice(0, i);
        let rest = perm.slice(i);
        yield [...start, first, ...rest];
      }
    }
  }
}

const arr = ['A', 'a', 'B', 'b', 'C', 'c', 'd', 'e'];
const results = new Set();

for (let subset of subsets(arr)) {
  if (subset.length) {
    for (let permut of permutations(subset)) {
       results.add(permut.join(''));
    }
  }
}

console.log([...results]);

Answer 4

Вы можете сначала сгруппировать одни и те же элементы и сосчитать их, в результате чего получится такая таблица:

 1 | 2 | 3 | 4
 1 |    | 3 | 4
 1

(1 дублируется дважды, 3 и 4 раза)

Теперь вы можете начатьи возьмите первые четыре элемента, затем 3 во втором ряду, а затем один в последнем ряду, в результате чего

 [[1, 2, 3, 4], [1, 3, 4], [1]]

Теперь, чтобы получить следующую комбинацию, просто возьмите 3 из первого ряда,и пусть другие значения перемещаются вверх:

 1 |   | 3 | 4
 1 |   |    | 4

, теперь снова вынимаем строки, и вы получаете

 [[1, 2, 3], [1, 3, 4], [1, 4]]

Теперь повторите этот паттерн с первой строкой (дубль 2, 1)и так далее, также повторите это со строками, тогда вы должны получить результат, которого хотите достичь.

 const counts = new Map;

 for(const value of  [1, 1, 1, 2, 3, 3, 4, 4])
   counts.set(value, (counts.get(value) || 0) + 1);

 const result = [];

 for(let combo = 0; combo < counts.size; combo++) {
   const subResult = [];
   const combos = [...counts];
   for(let i = 0; i <= combo; i++) combos[i][0] -= 1;
   subResult.push(combos.slice(0, combo).map(([_, value]) => value);
   while(combos.some(([count]) => count > 0)) {
      subResult.push(combos.filter(([count]) => count > 0).map(([_, value] => value));
   }
   result.push(subResult);
}

Answer 5

Это генерирует все возможные перестановки искомого результата, поэтому оно не отвечает на вопрос.

---

 function* combinations(combos) {
    yield combos;
    for(const [i1, group] of combos.entries()) {
       for(const [i2, group2] of combos.slice(i1 + 1).entries()) {
          if(group.some(v => group2.includes(v))) continue;
          yield* combinations([
            ...combos.filter((_, index) => index !== i1 && index !== i2), 
            [...group, ...group2]
         ]);
       }
    }
}

 console.log([...combinations([1, 2, 3, 4, 1].map(v => ([v])))]);

Вы можете начать с массива с комбинациями, которые содержат только один элемент, а затем перейти кэти комбинации и объединить два массива из них, действовать рекурсивно.

Детская площадка