машинопись: получить все комбинации фиксированной длины без повторов

Question

У меня есть следующий ввод:

interface Option{
  name:string
  travelMode:string
}

const options:Option[] = [
  {
    name:"john",
    travelMode:"bus"
  },
  {
    name:"john",
    travelMode:"car"
  },
  {
    name:"kevin",
    travelMode:"bus"
  },
  {
    name:"kevin",
    travelMode:"car"
  },
]

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

const getCombinations=(options:Option[],startIndex:number,combination:Option[],combinationSize:number)=>{
  if (combination.filter(e => e!==undefined).length === combinationSize)
  {
    console.log(combination)
  }
  else if (startIndex<options.length){
    combination[startIndex]=undefined
    getCombinations(options,startIndex+1,combination,combinationSize)


    combination[startIndex]=options[startIndex]
    getCombinations(options,startIndex+1,combination,combinationSize)
  }
}

getCombinations(options,0,[],2)

Это кажется, работает хорошо, я получаю следующий вывод:

[
  undefined,
  undefined,
  { name: 'kevin', travelMode: 'bus' },
  { name: 'kevin', travelMode: 'car' }
]
[
  undefined,
  { name: 'john', travelMode: 'car' },
  undefined,
  { name: 'kevin', travelMode: 'car' }
]
[
  undefined,
  { name: 'john', travelMode: 'car' },
  { name: 'kevin', travelMode: 'bus' },
  undefined
]
[
  { name: 'john', travelMode: 'bus' },
  undefined,
  undefined,
  { name: 'kevin', travelMode: 'car' }
]
[
  { name: 'john', travelMode: 'bus' },
  undefined,
  { name: 'kevin', travelMode: 'bus' },
  undefined
]
[
  { name: 'john', travelMode: 'bus' },
  { name: 'john', travelMode: 'car' },
  undefined,
  undefined
]

Однако у меня есть один сомнение и одна оставшаяся проблема :

Мои сомнения : почему все напечатанные комбинации имеют длину 4, мое условие прерывания должно обычно останавливать рекурсию, если у нас уже есть 2 определенных элемента: я не понимаю, почему последняя комбинация, напечатанная в моих выходных данных, содержит 4 элемента (первые 2 определены, а остальные 2 не определены) => Боюсь, что моя программа продолжает повторяться, даже если в ее комбинации уже 2 элемента, а это не то, что я хочу

Осталось задача : я не хочу вычислять комбинацию, где имя одно и то же, я хочу только комбинацию с двумя разными именами (Джон и Кевин, но не Джон и Джон или Кевин и Кевин). Сначала я подумал о том, чтобы сохранить свою программу, вычисляя все, и просто удалить в конце комбинацию с дублированными именами, но я быстро понял, что это не лучшее решение, особенно когда в моих параметрах ввода будет гораздо больше данных (другие лица и другие индивидуальные варианты). Поэтому я попробовал следующее решение (остановите программу, если мы уже посетили человека):

const getCombinations=(options:Option[],startIndex:number,combination:Option[],combinationSize:number)=>{
  if (combination.filter(e => e!==undefined).length === combinationSize)
  {
    console.log(combination)
  }
  else if (startIndex<options.length){
    combination[startIndex]=undefined
    getCombinations(options,startIndex+1,combination,combinationSize)

    let individualAlreadyVisited = false
    if (startIndex>0)
    {
      for (let i =0;i<startIndex;i++)
      {
        if (combination[i] && combination[i].name===options[startIndex].name)
        {
          individualAlreadyVisited=true
          break
        }
      }
    }

    if (!individualAlreadyVisited)
    {
      combination[startIndex]=options[startIndex]
      getCombinations(options,startIndex+1,combination,combinationSize)
    }
  }
}

getCombinations(options,0,[],2)

Но это не работает должным образом, я получаю следующий вывод:

[
  undefined,
  undefined,
  { name: 'kevin', travelMode: 'bus' },
  { name: 'kevin', travelMode: 'car' }
]
[
  undefined,
  { name: 'john', travelMode: 'car' },
  undefined,
  { name: 'kevin', travelMode: 'car' }
]
[
  undefined,
  { name: 'john', travelMode: 'car' },
  { name: 'kevin', travelMode: 'bus' },
  undefined
]
[
  { name: 'john', travelMode: 'bus' },
  undefined,
  { name: 'kevin', travelMode: 'bus' },
  undefined
]

1. У меня все еще есть комбинация с дублированными именами, см. Первый элемент

2. Я вижу некоторую пропущенную комбинацию, например, не отображается следующее:

    { name: 'john', travelMode: 'bus' },
    { name: 'kevin', travelMode: 'car' }
   

Заранее спасибо за помощь, я потратил несколько часов, пытаясь понять и получить то, что я хочу.

Answer 1

Я думаю, что путаница возникает из-за изменения массива во время рекурсивных шагов. Это делает код трудным для понимания и сложным для отладки.

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

 function* combine<T>(array: T[], n: number, start = 0, prev: T[] = []) {
   if(n <= 0) {
     yield prev;
     return;
   }

   for(let i = start; i <= array.length - n; i++) {
     yield* combine(array, n - 1, i + 1, [...prev, array[i]]);
   }
 }

 const result = [...combine([1, 2, 3, 4], 2)];

Чтобы удовлетворить ваши дополнительные требования, вы можете пропустить элементы, которые уже включены, например:

   if(prev.some(el => compare(el, array[i]))) continue;