Я пытаюсь сгенерировать неупорядоченные пары непересекающихся подмножеств множества S целых чисел. Как показано в [1], когда S состоит из n целых чисел, мы генерируем около 3 n / 2 пар. Теперь я знаю, как сгенерировать все 2 n подмножеств S (т. Е. Набор мощности S), и для каждого подмножества (состоящего из k целых чисел) я мог бы, таким образом, сгенерировать kC2 (k выберите 2) возможных пар , Но это неэффективно, потому что пары будут генерироваться более одного раза.
Поэтому мне интересно, есть ли какой-нибудь эффективный (рекурсивный) способ генерирования этих пар подмножеств из S? Я не смог найти ни одной существующей реализации, и мои собственные попытки с использованием, например, itertools Python пока не увенчались успехом.
[1] Общее количество неупорядоченных пар непересекающихся подмножеств S (MathOverflow) )