Я думаю, что это интересная проблема, которая требует умного динамического программирования. Однако я бы начал с некоторой простой грубой силы, а затем попытался бы ее уточнить. Насколько я понимаю ваш вопрос, вы в некоторой степени находитесь на этом этапе и пытаетесь найти способ перечислить все возможные пары.
Визуализируйте это
Для 4 учеников у вас есть три возможных комбинации
(0 1) (2 3) (0 2) (1 3) (0 3) (1 2)
1 2 3
0 x o o o x o o o x
1 o o o x x o
2 x o o
Обратите внимание, что нам нужно нарисовать только половину матрицы, потому что она симметрична (если 1 в паре с 2, то и 2 в паре с 1). Мы также можем игнорировать диагональ. Уже с 4 учениками это выглядит несколько сложно. Итак, давайте прямо.
Counting
Допустим, у вас есть N учеников, еще не назначенных для пары. Сколько комбинаций? Давайте назовем это C(N) ...
Для 2 студентов существует только одна комбинация, следовательно, C(2)= 1.
Для более чем двух не назначенных учеников мы можем выбрать первого ученика без потери общности. Есть еще N-1 других ученика, с которыми мы могли бы связать его, следовательно, всего C(N) = N-1 * C(N-2).
Давайте сделаем это немного конкретнее, перечислив цифры:
N N-1 C(N)
2 1 1
4 3 3
6 5 15
8 7 105
...
n n-1 (n-1)!!
Теперь мы уже знаем, как их считать. Есть 105 возможностей для 8 студентов. И вообще для n студентов есть (n-1)!! возможности (x!! == x*(x-2)*(x-4)*...).
Построив
Уже при подсчете мы использовали следующую стратегию для построения решения:
- Выберите первого свободного ученика
- Выберите одного из других бесплатных учеников
- Повторите с остальными
Очевидно, нам нужно n/2 шагов, чтобы все студенты были назначены в пару. Давайте рассмотрим пример. С 6 студентами у нас есть
( 5 ) * ( 3 ) * ( 1 )
возможные комбинации. Затем мы понимаем, что всегда можем использовать индекс, чтобы перечислять только тех студентов, которые еще доступны. Следовательно, мы должны выбрать индексы
[0...4] x [0...2] x [0]
Теперь, если, например, вы хотите узнать, что такое 5 -ая комбинация, вы можете получить ее следующим образом ...
Как только мы выберем первую пару, для второго индекса все еще будет 3 возможных вариантов выбора (только один, чтобы сделать последнюю пару из двух доступных учеников). Следовательно, вы получаете индексы как
x0 = 5/3; // -> 1
x1 = (5-x0)/1; // -> 2
Т.е. это было бы
- Мы выбираем первого студента для первой пары:
0
- Доступные студенческие сети на данный момент:
available = {1,2,3,4,5}
- Мы выбираем
available[x0], чтобы связать его с 0: (0 2)
- Доступные студенты на данный момент:
available = {1,3,4,5}
- Мы выбираем первую доступную для следующей пары:
1
- Доступные студенты на данный момент:
available = {3,4,5}
- Мы выбираем
available[x1], чтобы связать его с 1: (1 5)
- Только две осталось для последней пары
(3 4)
-> Сопряжение с индексом 5 равно (0 2)(1 5)(3 4).
Обратите внимание, что это может быть не самым эффективным способом, если реализовано слишком буквально, хотя это может быть отправной точкой.
код
Для подсчета комбинаций нам нужна функция x!! (!! в том смысле, как описано выше):
size_t double_fac(int n){
size_t result = 1;
while(n > 0) {
result*=n;
n-=2;
}
return result;
}
Используя это, я могу вычислить общее количество комбинаций
size_t total_number_of_combinations(size_t n_students){
return double_fac(n_students-1);
}
Мне понадобится функция, чтобы найти индекс n-го, еще не назначенного студента, для этого я буду использовать некоторые вспомогательные функции:
template <typename IT>
IT find_skip(IT begin,IT end,size_t skip,typename IT::value_type x){
if (skip){
return find_skip( ++ std::find(begin,end,x), end, skip-1,x);
} else {
return std::find(begin,end,x);
}
}
template <typename IT>
size_t find_skip_index(IT begin,IT end,size_t skip,typename IT::value_type x){
return std::distance(begin,find_skip(begin,end,skip,x));
}
Также я буду использовать плоский индекс, а затем расширю его, как указано выше (на самом деле мне не очень нравится приведенное выше объяснение, но я надеюсь, что оно достаточно убедительно ...):
std::vector<size_t> expand_index(size_t n_students, size_t flat_index){
std::vector<size_t> expanded_index;
auto students_to_be_assigned = n_students;
for (unsigned step=0;step<n_students/2;++step){
int size_of_subspace = total_number_of_combinations(students_to_be_assigned-2);
auto x = flat_index / size_of_subspace;
expanded_index.push_back(x);
flat_index -= x*size_of_subspace;
students_to_be_assigned-=2;
}
return expanded_index;
}
В двух словах: на каждом этапе я буду выбирать партнера для первого бесплатного студента. Для flat_index == 0 первая пара - (0 1). Поскольку после выбора этой пары есть комбинации size_of_subspace == total_number_of_combinations(n_students-2), индекс выбора (0 2) в качестве первой пары равен flat_index==size_of_subspace. Однако, пожалуйста, не смущайтесь, я не преобразую flat_index непосредственно в индекс студентов, а скорее expandend_index == n относится к n -ому, еще не назначенному студенту.
Собираем это вместе:
using combination = std::vector<std::pair<size_t,size_t>>;
combination nth_combination(size_t n_students,size_t flat_index){
combination result;
auto expanded_index = expand_index(n_students,flat_index);
std::vector<bool> available(n_students,true);
for (const auto& index : expanded_index) {
std::pair<size_t,size_t> next_pair;
next_pair.first = find_skip_index(available.begin(),available.end(),0,true);
available[next_pair.first] = false;
next_pair.second = find_skip_index(available.begin(),available.end(),index,true);
available[next_pair.second] = false;
result.push_back(next_pair);
}
return result;
}
Теперь снова возьмем n_students == 6 в качестве примера:
template <typename T>
void print_pairs(const T& t){
for (auto e: t) std::cout << "(" << e.first << "," << e.second << ") ";
std::cout << "\n";
}
int main(){
size_t n_students = 6;
for (size_t i=0;i<total_number_of_combinations(n_students);++i){
std::cout << i << "\t";
print_pairs(nth_combination(n_students,i));
}
}
печатает:
0 (0,1) (2,3) (4,5)
1 (0,1) (2,4) (3,5)
2 (0,1) (2,5) (3,4)
3 (0,2) (1,3) (4,5)
4 (0,2) (1,4) (3,5)
5 (0,2) (1,5) (3,4)
6 (0,3) (1,2) (4,5)
7 (0,3) (1,4) (2,5)
8 (0,3) (1,5) (2,4)
9 (0,4) (1,2) (3,5)
10 (0,4) (1,3) (2,5)
11 (0,4) (1,5) (2,3)
12 (0,5) (1,2) (3,4)
13 (0,5) (1,3) (2,4)
14 (0,5) (1,4) (2,3)
Надеюсь, с этим выводом алгоритм также станет более понятным.После выбора первой пары есть 3 возможностей для второй пары и только одна комбинация для последней.
Live Demo
Отказ от ответственности: Как уже упоминалось выше, я не утверждаю, что это эффективная реализация.Код скорее предназначен для подробной справочной реализации.Я в основном пересекаю дерево от корня до одного из его листьев для каждого flat_index.В следующей итерации можно было бы подумать о том, чтобы обходить дерево только столько, сколько необходимо, начиная с некоторой начальной конфигурации.