Учитывая массив хешей, я ищу способ выбрать случайное подмножество этих хешей, чтобы распределение атрибутов подмножества соответствовало желаемым процентам.
Например, для следующего массива:
[
{
question_id: 1,
grade: 1,
marks: [
{ topic: 'number', ao: 1 },
{ topic: 'ratios', ao: 2 }
]
},
{
question_id: 2,
grade: 3,
marks: [
{ topic: 'number', ao: 2 },
{ topic: 'number', ao: 2 }
]
},
{
question_id: 3,
grade: 2,
marks: [
{ topic: 'number', ao: 1 },
{ topic: 'geometry', ao: 1 },
{ topic: 'ratios', ao: 1 },
{ topic: 'number', ao: 2 },
{ topic: 'geometry', ao: 2 }
]
},
{
question_id: 4,
grade: 3,
marks: [
{ topic: 'number', ao: 1 },
{ topic: 'ratios', ao: 2 },
{ topic: 'geometry', ao: 2 },
{ topic: 'geometry', ao: 2 }
]
},
{
question_id: 5,
grade: 1,
marks: [
{ topic: 'ratios', ao: 1 },
{ topic: 'ratios', ao: 2 }
]
},
{
question_id: 6,
grade: 1,
marks: [
{ topic: 'number', ao: 1 },
{ topic: 'number', ao: 2 },
{ topic: 'number', ao: 2 },
{ topic: 'ratios', ao: 2 }
]
},
{
question_id: 7,
grade: 3,
marks: [
{ topic: 'number', ao: 2 }
]
},
{
question_id: 8,
grade: 3,
marks: [
{ topic: 'geometry', ao: 1 }
]
}
]
Я хотел бы найти случайную комбинацию, которая удовлетворяет следующему:
Общее количество марок = 10
50% оценок - номер темы
20% оценок - это тематические отношения
30% оценок - это геометрия темы
40% марок - 1
50% оценок - 2 класс
10% оценок - 3
50% марок - 1
50% марок - 2
Пример результата, который удовлетворяет этим требованиям:
[
{
question_id: 3,
grade: 2,
marks: [
{ topic: 'number', ao: 1 },
{ topic: 'geometry', ao: 1 },
{ topic: 'ratios', ao: 1 },
{ topic: 'number', ao: 2 },
{ topic: 'geometry', ao: 2 }
]
},
{
question_id: 6,
grade: 1,
marks: [
{ topic: 'number', ao: 1 },
{ topic: 'number', ao: 2 },
{ topic: 'number', ao: 2 },
{ topic: 'ratios', ao: 2 }
]
},
{
question_id: 8,
grade: 3,
marks: [
{ topic: 'geometry', ao: 1 }
]
}
]
В идеале, если бы комбинация не существовала для удовлетворения этих требований (с некоторой степенью допуска), я ожидала бы получить ошибку.
Мой первоначальный подход к проблеме состоял в том, чтобы найти все возможные комбинации вопросов, которые могли бы составить в общей сложности 10 баллов, а затем перебрать эти комбинации и проверить каждый из них, чтобы убедиться, что он удовлетворяет всем другим требованиям.
Я начал с этого алгоритма, который находит все возможные комбинации чисел из массива для суммирования до желаемой суммы:
def subset_sum(numbers, target, partial=[], result=[])
s = partial.inject 0, :+
if s == target
result << partial
end
return if s >= target
(0..(numbers.length - 1)).each do |i|
n = numbers[i]
remaining = numbers.drop(i+1)
subset_sum(remaining, target, partial + [n], result)
end
result
end
end
Однако в реальном приложении к моей проблеме я ожидаю, что массив вопросов будет иметь длину более 1000, а общее количество меток равно 40. Для этих чисел это решение слишком недостаточно оптимизировано, а время выполнения очень велико.