Самый эффективный способ выбрать уникальные строки из взвешенных категорий

Question

Настройка:

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

Пример:

• Категории: a, b, c
• Строки:
  • a_001, a_002, a_003
  • b_001, b_002, b_003
  • c_001, c_002, c_003
• Вес:
  • a: 1
  • b: 2
  • c: 1

Задание:

Получить массив уникальных строк, 1 из категории a, 2 из категории b и 1 из категории c. Количество выбранных строк из категории не обязательно должно совпадать с weightedNumber. Вес должен быть просто учтен (хотя сильно) при выборе строк. Однако, если это невозможно, то это не конец света. Однако количество выбранных строк ДОЛЖНО быть верным.

Проблемы:

• Вес может быть 10, но в этой категории есть только 3 уникальные строки (в этом случае она должна быть заполнена строками из других категорий в зависимости от их веса)
• Я работаю с Firestore, поэтому я могу выбрать только одну случайную строку за раз, и у меня нет доступа к количеству строк в данной категории

Моя попытка:

function pickStrings(numberOfStrings, arrCategories) {
  // Calculates the weight of each category
  // Sets initial weight and stringsleft to weightTotal and numberOfStrings
  // Iterates over the categories:
  //    selectedStrings.push(...pickStringsFromCategory(calculatedNumberBasedOnWeight, categoryId))
  // returns selectedStrings
}

function pickStringsFromCategory(numberOfStrings, categoryid) {
  // Create a map of picked strings
  // Randomly pick a string from that category
  // Checks if the string was picked already
  // Tries again (up to 10 times) if the string was already picked
}

Однако, это просто нехорошо. Попытка 10 раз является искусственным числом, и если категория с только 1 строкой и weightedNumber, равным 10, является последней, число выбранных строк меньше, чем numberOfStrings.

Есть идеи, как улучшить этот алгоритм?

Answer 1

Здесь возможен подход:

var arr = [
  ["a_001", "a_002", "a_003"],
  ["b_001", "b_002", "b_003"],
  ["c_001", "c_002", "c_003"]
];

var weights = [7, 2, 1];

var str = "";
weights.map((o, i) => {

  let curr = i;
  let p = 0;
  for (let j = 0; j < o; j++) {
    if (arr[curr][p]) {//this could be and ajax, function, whatever
      str += arr[curr][p] + " ";//this is an assumption
      p++;
    } else { //this happens when we didn't find a string into such category 
      curr = curr + 1; //we move one category
      p = 0;//firs element in the next category
      j--;//move back because we didn't finish
    }
  }

})

console.log(str);