Найти случайную комбинацию массивов общей длиной 10 и разбить на две группы по 5

Question

Допустим, у меня есть массив с массивами, например:

const array = [
    ['a', 'b', 'c'],
    ['d', 'e'],
    ['f', 'g', 'h', 'i', 'j'],
    ['k'],
    ['l'],
    ['m'],
    ['n', 'o', 'p'],
    ['q', 'r', 's'],
    ['t', 'u', 'v'],
    ['x']
];

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

• Общая длинаиз всех выбранных комбинаций всегда должно быть 10. Возможным результатом могут быть первые 3 элемента array
• Выбранные комбинации должны быть в состоянии разбить на две группы по 5. И снова первые 3предметы будут соответствовать этому условию: length из ['a', 'b, 'c'] + length из ['d', 'e'] равно 5, и в то же время длина ['f', 'g', 'h', 'i', 'j'] равна 5. Это две группы 5. С другой стороны, последние 4 элемента array не смогут выполнить это условие, даже если они соответствуют первому (общая длина = 10).

Это может помочь понять цель этого: у меня есть небольшая многопользовательская игра. Для игр нужны 2 команды по 5 игроков. И игроки могут войти в игру с другом, чтобы играть в одной команде (или даже с 5 друзьями, мгновенно заполнив всю команду).

Идея: игроки нажимают «Старт». Тогда моя функция поместит их в массив, подобный приведенному выше. Каждый раз, когда происходил толчок, запускалась функция игрока / команды (которую я прошу о вашей помощи). Если совпадение будет найдено, игра начнется.

У меня такое ощущение, что лучше всего это сделать с помощью какой-нибудь рекурсивной функции, но у меня в голове проблемы с ее выяснением.

---

Через пару часов вот решение, которое я нашел. Пройдены все мои тесты.

//const { shuffle, flatten } = require('lodash');

const pool = [
    ['a', 'b', 'c'],
    ['d', 'e'],
    ['f', 'g', 'h', 'i', 'j'],
    ['k'],
    ['l'],
    ['m'],
    ['n', 'o', 'p'],
    ['q', 'r', 's'],
    ['t', 'u', 'v'],
    ['x']
];

function getMaxPickSize ( draw ) {
    let x = 5;
    let y = 5;

    draw.forEach( pick => {

        if ( x - pick.length >= 0 ) {
            x -= pick.length;

        } else if ( y - pick.length >= 0 ) {
            y -= pick.length;
        }

    });

    return Math.max(x,y);
}


function doDraw( pool ) {
    //no need to move further if there arent even 10 players
    if ( _.flatten(pool).length < 10 ) {
        return false;
    }

    // keep register of all draws and pools, and items. if we 
    // figure out an attempt doesnt work, we can go back anytime
    // and skip picks that dont work
    let prevs = [
        // array of objects that will look like this.
        // {   
        //     pool: [],
        //     draw: [],
        //     skip: []
        // }
        // ...
    ];

    //let's try. First step, shuffle the pool;
    pool = _.shuffle(pool);

    function doIt( curr_pool, curr_draw = [], skip_items_w_length ) {

        let new_pool = [...curr_pool];
        let new_draw = [...curr_draw];
        let pick;

        if ( skip_items_w_length == undefined ) {
            //in first loop it starts here
            //if we happen to have luck and fill the draw in
            //one go, the else statement below will never execute
            pick = new_pool.shift();

        } else {

            let to_skip = prevs[prevs.length - 1].skip;
            to_skip.push(skip_items_w_length);

            pick = _.find(new_pool, item => !to_skip.includes(item.length) );

            if ( pick ) {
                new_pool.splice(new_pool.indexOf(pick), 1);

            } else {
                if ( !prevs.length ) {
                    return false;
                }

                let prev = prevs.pop();
                let prev_pool = prev.pool;
                let prev_draw = prev.draw;
                let last_item_in_prev_draw = prev_draw.pop();

                return doIt(prev_pool, prev_draw, last_item_in_prev_draw.length );
            } 
        }

        new_draw = [...curr_draw, pick];

        //if draw is complete, return it
        if ( _.flatten(new_draw).length === 10 ) {
            return new_draw;
        }


        //else draw process continues
        //find items in pool that can still fit into draw
        const max_pick_size = getMaxPickSize(new_draw);
        new_pool = new_pool.filter(item => item.length <= max_pick_size);

        //if items dont contain enough players to fill remaining spots,
        //repeat this exact step, ignoring items without pick's length
        //as none of the remaining picks can follow. if we discover in
        // later repeats that no pick allows other picks to follow
        // we'll go back 1 step, using previous pool and draw, and
        // ignoring all picks with the associated picks length
        if ( _.flatten(new_pool).length < 10 - _.flatten(new_draw).length ) {
            return doIt(curr_pool, curr_draw, pick.length);
        }


        prevs.push({
            pool: curr_pool,
            draw: curr_draw,
            skip: []
        });

        return doIt(new_pool, new_draw);
    }


    return doIt(pool);

}

const draw = doDraw( pool );

Спасибо, ребята!

Answer 1

Перемешайте массив, затем уберите уникальные группы, пока не достигнете пяти:

const array = [
    ['a', 'b', 'c'],
    ['d', 'e'],
    ['f', 'g', 'h', 'i', 'j'],
    ['k'],
    ['l'],
    ['m'],
    ['n', 'o', 'p'],
    ['q', 'r', 's'],
    ['t', 'u', 'v'],
    ['x']
];


function shuffle(arr) { /* Shuffling algorithm here */ }

shuffle(array);

// Extracts arrays with exactly "count" elements, excluding all elements in "exclude" and starting at "start" in the array
// If no combination was found, return undefined
function takeOut(array, count, start = 0, exclude = []) {
  // Base case: Count wasn't reached exactly, abort here
  if(count < 0) return;
  // Base case: Combination was found, go up
  if(count === 0) return [];

  // Go over the array to find a matching combination
  for(let i = start; i < array.length; i++) {
    const current = array[i];
    // Skip elements that should be excluded
    if(exclude.includes(current)) continue;
    
    // Recursive call: Find more elements so that a group of "count" gets reached
    const rest = takeOut(array, count - current.length, i + 1, exclude);
    if(!rest) continue; // If this element can't be matched up, go on
    return [current, ...rest];
  }
}

// Our two teams:
const first = takeOut(array, 5);
const second = takeOut(array, 5, 0, first); // all from the first team can't be in the second one

console.log(first, second);

if(first && second)
   console.log("The game can start");

Answer 2

Я придумал решение, которое может быть не совсем тем, что вы хотели. Во всяком случае, я думаю, что это может помочь вам. Он находит все возможные композиции, и если вам нужна только одна, вы можете выбрать ее случайным образом. Я также использовал немного другую модель данных: объект, где ключи представляют размеры команд, а значения - это массивы команд с соответствующими размерами.

const UNITS_NUMBER = 2

// object format: { [number]: how-many-times-this-number-should-be-used }
const COMPOSE_VARIATIONS = [{1: 5}, {1: 3, 2: 1}, {1: 2, 3: 1}, {1: 1, 4: 1}, {1: 1, 2: 2}, {2: 1, 3: 1}, {5: 1}]

const parts = {
  1: [['k'], ['l'], ['m'], ['x']],
  2: [['d', 'e']],
  3: [['a', 'b', 'c'], ['n', 'o', 'p'], ['q', 'r', 's'], ['t', 'u', 'v']],
  4: [],
  5: [['f', 'g', 'h', 'i', 'j']],
}

function getAllCompositions(allParts, unitsNumber, composeVariations) {
  const result = []
  const usedPartsStack = []
  let units = [] 
  let currentIndex = 0
  let unitsComposed = 0
  while (currentIndex < composeVariations.length) {
    const variation = composeVariations[currentIndex]
    if (canCreateUnit(allParts, variation)) {
      const unit = getPartsForUnit(allParts, variation)
      units.push(flatten(unit))
      if (unitsComposed + 1 < unitsNumber) {
        usedPartsStack.push({ index: currentIndex, partsUsedForUnit: unit })
        allParts = removeUsedParts(allParts, variation)
        unitsComposed++
      } else {
        result.push([...units])
        units.pop()
        currentIndex++
      }
    } else {
      currentIndex++
    }
    while (currentIndex === composeVariations.length && usedPartsStack.length) {
      const { index, partsUsedForUnit } = usedPartsStack.pop()
      currentIndex = index + 1
      allParts = restoreUsedParts(allParts, partsUsedForUnit)
      unitsComposed--
      units.pop()
    }
  }
  return result
}

// checks if passed variation can be used to create unit from parts from allParts object
// unit is a group of parts that forms an array with total length of 5)
function canCreateUnit(allParts, variation) {
  return Object.entries(variation).every(([length, count]) => allParts[length].length >= count)
}

// get real parts from allParts object according to variation passed
function getPartsForUnit(allParts, variation) {
  const result = []
  Object.entries(variation).forEach(([length, count]) => {
    result.push(allParts[length].slice(0, count))
  })
  return result
}

// removes parts that were used for unit creation
function removeUsedParts(allParts, variation) {
  const result = { ...allParts }
  Object.entries(variation).forEach(([length, count]) => {
    result[length] = result[length].slice(count)
  })
  return result
}

// add parts to allParts object
function restoreUsedParts(allParts, parts) {
  const result = { ...allParts }
  parts.forEach((item) => {
    result[item[0].length] = [...item, ...result[item[0].length]]
  })
  return result
}

// removes one level of nesting in array
function flatten(partsForUnit) {
  const result = []
  partsForUnit.forEach(item => {
    result.push(...item)
  })
  return result
}

function print(compositions) {
  compositions.forEach(composition => {
    composition.forEach(unit => {
      console.log(unit)
    })
    console.log('=======================================')
  })
}

print(getAllCompositions(parts, UNITS_NUMBER, COMPOSE_VARIATIONS))