Особый алгоритм перебора всех подмножеств мультимножества

[arseniiv]

B@R5uk в сообщении #1287723 писал(а):

Возможно, это как раз из-за того, что я сделал описанную только что оптимизацию. С другой стороны, трудоёмкость разных шагов (в том числе в разных программах) может очень сильно отличаться, так что число шагов не самый надёжных показатель.

Понятно. У меня каждая строка с = или ? соответствует одному кусочку сравнения сумм, и строки с < могут вызвать несколько сравнений, являющихся ненужными, из-за того, что надо учесть изменение суммы (можно было бы в таком случае указывать, что сравнивать ничего не надо, но себе я посчитал это лишним).

grizzly в сообщении #1287752 писал(а):

Попросить у arseniiv алгоритм?

Ну, с ним ничего особенного кроме того, что перебираются мультимножества, и притом чрезмерные количества элементов не перебираются изначально.

grizzly в сообщении #1287752 писал(а):

Подозреваю, что он во всех отношениях оптимален.

Это лестная оценка, но я не думаю, что нельзя что-то подкрутить. Код можно увидеть и поиграть с ним и данными тут: https://try.ceylon-lang.org/?gist=2e273762ba5ce502b1782b30131b8650. Он не очень причёсанный, и даже именование вещей оставляет желать лучшего, и комментариев тоже нет (это всё надо честно признать, потому что я недавно пропонировал, что вообще любой код должен быть на уровне и остаюсь того же мнения). Также код мог бы быть короче, если бы я не отделил перебор (всё, что делает класс SubsetTraversal) от оценки (всё остальное в partitionsWithSum). Ну и вместо вызова функции там итератор, так что состояние ещё немного дополнительно фрагментировано.

[B@R5uk]

B@R5uk в сообщении #1287746 писал(а):

Осталось придумать, то именно...

Казалось бы лёгким движением руки брюки превращаются... простой заменой строчки
--index; на строчку
index = indexShifts[index];, где indexShifts — это заранее посчитанный массив преобразований индекса, мой уже почти готовый алгоритм превращается в полностью готовый и прекрасно справляется с повторяющимися элементами, пропуская комбинации как в этом примере:

abcDDefg

00000yyy
00001yyy
00011yyy
xxx11yyy
10011yyy
00101yyy
xxx01yyy
10001yyy-->+
00010yyy . |
xxx10yyy . |
10010yyy . v
00100yyy<--+
xxx00yyy
10000yyy

abcDDDefg

000000yyy
000001yyy
000011yyy
001111yyy
xxx111yyy
100111yyy
001011yyy
xxx011yyy
100011yyy-->+
000101yyy . |
xxx101yyy . |
100101yyy . v
001001yyy<--+
xxx001yyy
100001yyy-->+
000010yyy . |
000110yyy . |
xxx110yyy . |
100110yyy . |
001010yyy . |
xxx010yyy . |
100010yyy . |
000100yyy . |
xxx100yyy . |
100100yyy . v
001000yyy<--+
xxx000yyy
100000yyy

Но нет же, если повторяется самый последний элемент, то этот приём не работает:

AAbcd

00yyy
01yyy
11yyy
10yyy

AAAbcd

000yyy
001yyy
011yyy
111yyy
101yyy-->+
010yyy . |
110yyy . v
100yyy<--+

Вечно с этими крайними случаями одни проблемы! Как не охота переписывать весь алгоритм с начала для работы с системой переменной "-ичности". Двоичная так хороша, плюс не так то просто придумать обобщённое правило перебора.

[Dmitriy40]

B@R5uk в сообщении #1287874 писал(а):

Но нет же, если повторяется самый последний элемент, то этот приём не работает:
Вечно с этими крайними случаями одни проблемы!

На такой случай есть стандартный способ обхода этих грабель: добавьте фиктивный элемент после конечного. Обычно его можно достаточно просто вычислить по входным данным (а иногда он и вовсе просто константа). А при выводе его игнорировать или вычитать из количества. Зато все внутренности принимают красивый симметричный вид.
Например такой подход распространён в задачах поиска, чтобы не обрабатывать в глубоком сложном внутреннем цикле ещё и ситуацию отсутствия искомого элемента (без чего многие алгоритмы зацикливаются), его перед поиском насильно добавляют во входной поток, а на выходе проверяют не его ли нашли. Сложность проверки снижается с $O(n)$ до $O(1)$, часто это очень много.

[B@R5uk]

Dmitriy40, спасибо за интересную идею! Но тут есть проблема, заключающаяся в экспоненциальной сложности перебора. Добавление одного элемента увеличивает общее число итераций в два раза. При этом половина из них оказывается ненужными и отбрасывается. Надо подумать, стоит ли овчинка выделки.

[Dmitriy40]

B@R5uk
Вы не так поняли, я не предлагал добавить ещё один вес для распределения, я предлагал добавить ещё одно состояние рюкзака ($-\infty$кг или $+\infty$кг, смотря в какую сторону идёте), гарантированно не встречающееся в переборе. Ну или разрешить указателю указывать за пределы массива. На программу это повлияет ровно в двух местах: в инциализации indexShifts[] и в самом конце перебора, и то и другое выполнится ровно один раз. На внутренности же повлияет в сторону упрощения. Правда программу я вообще не смотрел.

[mustitz]

А мы уже в обсуждение рюкзака скатились? Изначально вроде речь шла про общий перебор подмножеств. При решении задачи об рюкзаке есть много эвристик, которые не относятся к другим переборным задачам :)

[B@R5uk]

Dmitriy40 в сообщении #1288141 писал(а):

Ну или разрешить указателю указывать за пределы массива.

Именно так по началу я и хотел это реализовать. Но это группа первых элементов всё равно будет особенной. Вот два наглядных примера:

000000
000001
000011
000111
001111
011111
111111
111110
111100
111000
110000
100000

000000
000001
000011
000111
001111
011111
111111
000010
000110
001110
011110
111110

В первом случае первый элемент уникальный, а все пять остальных одинаковы. Во втором случае — наоборот: уникальный последний, а первые пять одинаковы. Во втором случае при переходе между комбинациями
111111
000010
осуществляется сброс вхождения всех пяти элементов, что надо делать во вложенном цикле. Ни в каком другом случае этого делать не надо: повторяющиеся элементы перебираются как обычно по одному. Здесь только один выход: хранить счётчики повторов, а перебор делать не в двоичной системе счисления, а в системе счисления с переменным основанием (своим для каждого разряда — числа вхождений повторов). Тогда тогда обработка повторов первого и всех остальных элементов будет унифицирована: запись нового значения в разряд.

-- 29.01.2018, 11:58 --

mustitz в сообщении #1288186 писал(а):

А мы уже в обсуждение рюкзака скатились? Изначально вроде речь шла про общий перебор подмножеств. При решении задачи об рюкзаке есть много эвристик, которые не относятся к другим переборным задачам :)

Вообще-то я с самого начала указал, что мне нужен особый вариант перебора для свободного осуществления этих эвристик:

B@R5uk в сообщении #1286815 писал(а):

Такой способ перебора оптимален в том смысле, что он позволяет оценить характеристику полученного подмножества и, если оно неудовлетворительно, пропустить все неудовлетворительные подмножества, которые порождаются текущим (их количество указано в пятом столбце и равно $2^M-1$, где $M$ — число не рассмотренных на данном шаге элементов исходного множества) и перейти к просмотру следующего потенциально удовлетворительного подмножества (его номер указан в четвёртом столбце).

Как потом оказалась подобный вариант перебора позволяет легко и естественно реализовать не только отсечение по превышению, но и отсечение не по недобору.

[B@R5uk]

B@R5uk в сообщении #1288195 писал(а):

Вот два наглядных примера:

Первый пример я не правильно изобразил. Правильно будет так:
000000
000001
000011
000111
001111
011111
111111
101111
100111
100011
100001
Очень похоже на то, как пропускаются недолёты, но здесь так выглядит перебор с повторяющимися элементами.

-- 30.01.2018, 00:44 --

Запилил новый код для перечисления всех комбинаций с учётом повторений:

Используется синтаксис Java

import java.util.*;

public class StudySubsetSearch13 {
        
        private static final Random rng = new Random();
        private static final int maxRand = 4;
        private static final int size = 7;
        private static final int[] values = new int[size];
        private static final int[] entryFlags = new int[size];
        private static final int[] nextEntryReference = new int[size];
        private static final int[] previousGroupIndex = new int[size];
        private static int index;
        private static int nextEntryIndex;
        private static int frontRepetitionIndex;
        
        public static void main(String[] args) {
                int n, value, lastValue, sum, tagetSum;
                boolean isFlagged;
                for (n = 0; size > n; n++) {
                        values[n] = 1 + rng.nextInt(maxRand);
                }
                Arrays.sort(values);
                
                index = -1;
                previousGroupIndex[0] = index;
                lastValue = values[0];
                sum = lastValue;
                frontRepetitionIndex = 0;
                isFlagged = true;
                for (n = 1; size > n; n++) {
                        value = values[n];
                        sum += value;
                        if (lastValue != value) {
                                index = n - 1;
                                isFlagged = false;
                        }
                        if (isFlagged) {
                                ++frontRepetitionIndex;
                        }
                        previousGroupIndex[n] = index;
                        lastValue = value;
                }
                tagetSum = sum / 3 + rng.nextInt(maxRand);
                
                System.out.println(Arrays.toString(values));
                System.out.println(Arrays.toString(previousGroupIndex));
                System.out.println(tagetSum);
                System.out.println();
                System.out.println(frontRepetitionIndex);
                System.out.println();
                
                nextEntryIndex = size;
                index = size - 1;
                while (true) {
                        display(entryFlags);
//                      display(nextEntryReference);
                        if (-1 == index) {
                                index = 0;
                                while (true) {
                                        entryFlags[index] = 0;
                                        if (frontRepetitionIndex == index) {
                                                break;
                                        }
                                        ++index;
                                }
                                index = nextEntryReference[index];
                                if (size == index) {
                                        break;
                                }
                                entryFlags[index] = 0;
                                nextEntryIndex = nextEntryReference[index];
                                index = previousGroupIndex[index];
                        }
                        entryFlags[index] = 1;
                        nextEntryReference[index] = nextEntryIndex;
                        nextEntryIndex = index;
                        --index;
                }
        }
        
        private static void display(int[] array) {
                int n, size;
                size = array.length;
                for (n = 0; size > n; ++n) {
                        System.out.print(array[n]);
                }
                System.out.println();
        }
}

Исключительно учёт повторений, никаких пропусков по недолёту/перелёту, даже искомые суммы не считаются. Результаты примерно такие:

(ВАРИАНТ ОДИН)

[2, 2, 2, 2, 3, 3, 4]
[-1, -1, -1, -1, 3, 3, 5]
6

3

0000000
0000001
0000011
0000111
0001111
0011111
0111111
1111111
0001011
0011011
0111011
1111011
0001001
0011001
0111001
1111001
0000010
0000110
0001110
0011110
0111110
1111110
0001010
0011010
0111010
1111010
0001000
0011000
0111000
1111000

(ВАРИАНТ ДВА)

[2, 3, 3, 3, 4, 4, 4]
[-1, 0, 0, 0, 3, 3, 3]
10

0

0000000
0000001
0000011
0000111
0001111
0011111
0111111
1111111
1011111
1001111
1000111
0001011
0011011
0111011
1111011
1011011
1001011
1000011
0001001
0011001
0111001
1111001
1011001
1001001
1000001
0001000
0011000
0111000
1111000
1011000
1001000
1000000

(ВАРИАНТ ТРИ)

[2, 2, 3, 3, 3, 3, 4]
[-1, -1, 1, 1, 1, 1, 5]
6

1

0000000
0000001
0000011
0000111
0001111
0011111
0111111
1111111
0101111
1101111
0100111
1100111
0100011
1100011
0100001
1100001
0000010
0000110
0001110
0011110
0111110
1111110
0101110
1101110
0100110
1100110
0100010
1100010
0100000
1100000

Осталось реализовать эвристические пропуски...

-- 30.01.2018, 01:01 --

В конце-концов я решил использовать всё-таки двоичную систему, а не систему с переменным основанием. И не потому, что в двоичной большая часть уже работает (код приходится всё равно с нуля переписывать). В системе с переменным основанием на каждой итерации необходимо делать по крайней мере одну дополнительную проверку: при счёте вперёд — не превысил ли счётчик текущего слагаемого максимальное количество повторов этого слагаемого, а при счёте назад не равен ли он нулю. В двоичной же всё гораздо проще: записали единицу — перешли к следующему элементу, записали ноль — тоже перешли к следующему элементу. Никаких проверок, никаких лишних затрат времени. И кода меньше в разы. Как только подумаю, в каком виде хранить кумулятивные суммы для отсечения по недолёту — волосы дыбом становится. Так что мой выбор однозначен: двоичное перечисление, и ничего другого!

[arseniiv]

B@R5uk в сообщении #1288375 писал(а):

В системе с переменным основанием на каждой итерации необходимо делать по крайней мере одну дополнительную проверку: при счёте вперёд — не превысил ли счётчик текущего слагаемого максимальное количество повторов этого слагаемого, а при счёте назад не равен ли он нулю.

Мне удалось ни разу не проверять, не равен ли он нулю. Код свидетель!

-- Вт янв 30, 2018 02:30:56 --

B@R5uk в сообщении #1288375 писал(а):

Никаких проверок, никаких лишних затрат времени.

Хм, тут ведь не всё тривиально, с современными-то процессорами и рантаймами, чтобы вот так надеяться, что если одной проверкой меньше, всё будет лучше.

B@R5uk в сообщении #1288375 писал(а):

Как только подумаю, в каком виде хранить кумулятивные суммы для отсечения по недолёту — волосы дыбом становится.

Я брал для всех вхождений каждого элемента скопом — вроде вполне естественно.

[Dmitriy40]

Двоичная система удобна ещё и тем что в ней есть красивые трюки, например:

Используется синтаксис C

y=x&(-x);//получение маски младшей установленной 1, она же равна количеству перебора по младшим нулевым битам, т.е. прямо по числу можно очень просто получить сколько раз его можно повторить перебирая лишь все возможные комбинации вида xxxx1000..xxxx1111
z=y-1;//из неё же можно тривиально получить и маску перебираемых битов, или превратить число вида yyyy1000 в число вида yyyy0111 (младшую единицу в ноль, а всё правее неё в единицы)
t=x+1;//превратить число вида xxx00111 в число вида xxx01000 (младший ноль в единицу, а всё правее него в нули)
w=x|(x+1);//Смена самого правого 0 на 1

Это например иногда позволяет обойтись без цикла поиска младшей 1 или младшего 0 чтобы их уменьшить/увеличить, или просто узнать сколько повторов можно безопасно перепрыгнуть. Чуть подробнее есть хотя бы здесь.

[B@R5uk]

arseniiv в сообщении #1288407 писал(а):

Код свидетель!

Увы, с моим мобильным интенетом (10-15 килобайт/сек максимум), та онлайн среда разработки не прогрузилась. Хотя мне очень интересно, как это у вас получилось.

Dmitriy40 в сообщении #1288423 писал(а):

Двоичная система удобна ещё и тем что в ней есть красивые трюки

Ну, в моём случае каждый бит представления хранится в отдельной ячейке массива, так что эти трюки мне не приходятся. Последний трюк, я знаю, используется в дереве Фенвика для логарифмического времени подсчёта суммы подряд идущих элементов. В нём, кстати, получается структура очень похожая на биномиальные деревья, что в самом начале mustitz предлагал. Только, поскольку элементов может быть произвольное число, а не только степень двойки, эти деревья слегка усечены.

[arseniiv]

B@R5uk в сообщении #1288448 писал(а):

Увы, с моим мобильным интенетом (10-15 килобайт/сек максимум), та онлайн среда разработки не прогрузилась.

Что ж вы сразу-то не сказали. Вот ссылка на только код (они синхронизированы друг с другом, так что если вдруг где-то будут изменения, отразится в обоих местах).

Конкретно о сравнении с нулём дело в том, что до него не доходит дело, потому что или раньше срабатывает отсечение по недостатку, или равенство (и отсечение части следующих вариантов). И только в противном случае функцией оценки будет возвращён Status.unknown, реакция на который — углубление (см. два лога на предыдущей странице; ему соответствует ?, предыдущим — очевидные < и =).

[B@R5uk]

arseniiv в сообщении #1288461 писал(а):

Вот ссылка
на только код

Ух! Другой язык, ничего не понимаю. Но спасибо, конечно.

[mustitz]

(Оффтоп)

Dmitriy40 в сообщении #1288423 писал(а):

Двоичная система удобна ещё и тем что в ней есть красивые трюки, например:

А вот и мой трюк для перевода всех сочетаний:

Используется синтаксис C

static inline uint64_t next_combination_mask(uint64_t x)                
{                                                                       
    uint64_t a = x & -x;                                                
    uint64_t b = x + a;                                                 
    uint64_t c = b ^ x;                                                 
    a <<= 2;                                                             
    c /= a;                                                            
    return b | c;                                                       
}

Например, чтобы перебрать все сочетания из пяти карт из колоды в 52 листа надо

Используется синтаксис C

    uint64_t current = 0x0F; // первая битовая маска;
    uint64_t last = 1 << 52; // 52-й бит появится только когда мы рассмотрим все комбинации из 52 карт, и перейдем к 53-й
    do {
        process_mask&#40;current&#41;; // что-то делаем...
        current = next_combination_mask&#40;current&#41;; // переходим к следующей руке
    } while &#40;current < last&#41;;

[B@R5uk]

Сделал таки пропуск перелётов в процессе поиска уникальных сумм с повторами:

Используется синтаксис Java

import java.util.*;

public class StudySubsetSearch14 {
        
        private static final Random rng = new Random();
        private static final int maxRand = 5;
        private static final int size = 10;
        private static final int[] values = new int[size];
        private static final int[] entryFlags = new int[size];
        private static final int[] nextEntryReference = new int[size];
        private static final int[] previousGroupReference = new int[size];
        private static int frontRepetitions, index, nextEntryIndex;
        private static int sum, tagetSum;
        
        public static void main(String[] args) {
                int n, value, lastValue, previousEntryIndex;
                int repetitions, subsetsNumber, subsetCount, matchCount;
                boolean isFlagged;
                for (n = 0; size > n; n++) {
                        values[n] = 1 + rng.nextInt(maxRand);
                }
                Arrays.sort(values);
                
                index = -1;
                previousGroupReference[0] = index;
                lastValue = values[0];
                sum = lastValue;
                isFlagged = true;
                repetitions = 0;
                subsetsNumber = 1;
                for (n = 1; size > n; n++) {
                        value = values[n];
                        sum += value;
                        if (lastValue != value) {
                                index = n - 1;
                                subsetsNumber *= repetitions + 2;
                                if (isFlagged) {
                                        frontRepetitions = repetitions;
                                        isFlagged = false;
                                }
                                repetitions = 0;
                        } else {
                                ++repetitions;
                        }
                        previousGroupReference[n] = index;
                        lastValue = value;
                }
                if (isFlagged) {
                        frontRepetitions = repetitions;
                }
                subsetsNumber *= repetitions + 2;
                tagetSum = sum / 3 + rng.nextInt(maxRand);
                
                System.out.println(Arrays.toString(values));
                System.out.println(Arrays.toString(previousGroupReference));
                System.out.println(frontRepetitions);
                System.out.println();
                
                nextEntryIndex = size;
                index = size - 1;
                sum = 0;
                subsetCount = 0;
                matchCount = 0;
                while (true) {
                        display(entryFlags, sum, tagetSum);
                        ++subsetCount;
                        if (tagetSum <= sum) {
                                if (tagetSum == sum) {
                                        System.out.print(" Match! ");
                                        ++matchCount;
                                } else {
                                        System.out.print("        ");
                                }
                                isFlagged = true;
                        } else {
                                System.out.print("        ");
                                isFlagged = false;
                        }
                        if (-1 == index) {
                                isFlagged = true;
                        } else if (isFlagged) {
                                System.out.print("overshot skipping");
                                previousEntryIndex = previousGroupReference[nextEntryIndex];
                                if (-1 != previousEntryIndex) {
                                        entryFlags[nextEntryIndex] = 0;
                                        sum -= values[nextEntryIndex];
                                        nextEntryIndex = nextEntryReference[nextEntryIndex];
                                        index = previousEntryIndex;
                                        isFlagged = false;
                                }
                        }
                        if (isFlagged) {
                                do {
                                        ++index;
                                        entryFlags[index] = 0;
                                        sum -= values[index];
                                } while (frontRepetitions > index);
                                index = nextEntryReference[index];
                                if (size == index) {
                                        System.out.println("end");
                                        break;
                                }
                                entryFlags[index] = 0;
                                sum -= values[index];
                                nextEntryIndex = nextEntryReference[index];
                                index = previousGroupReference[index];
                        }
                        entryFlags[index] = 1;
                        sum += values[index];
                        nextEntryReference[index] = nextEntryIndex;
                        nextEntryIndex = index;
                        --index;
                        System.out.println();
                }
                System.out.println();
                System.out.print("Subsets found: ");
                System.out.println(matchCount);
                System.out.print("Subsets searched: ");
                System.out.println(subsetCount);
                System.out.print("Subsets total number: ");
                System.out.println(subsetsNumber);
        }
        
        private static void display(int[] array, int sum, int tagetSum) {
                int n, size;
                size = array.length;
                for (n = 0; size > n; ++n) {
                        System.out.print(array[n]);
                }
                System.out.print(" -> ");
                System.out.print(String.format("%2d", sum));
                System.out.print(" (");
                System.out.print(tagetSum);
                System.out.print(")");
        }
}

Результаты примерно такие:

(Оффтоп)

[1, 1, 1, 1, 2, 2, 2, 3, 4, 4]
[-1, -1, -1, -1, 3, 3, 3, 6, 7, 7]
3

0000000000 -> 0 (11)
0000000001 -> 4 (11)
0000000011 -> 8 (11)
0000000111 -> 11 (11) Match! overshot skipping
0000001011 -> 10 (11)
0000011011 -> 12 (11) overshot skipping
0001001011 -> 11 (11) Match! overshot skipping
0001000011 -> 9 (11)
0011000011 -> 10 (11)
0111000011 -> 11 (11) Match! overshot skipping
0000000101 -> 7 (11)
0000001101 -> 9 (11)
0000011101 -> 11 (11) Match! overshot skipping
0001001101 -> 10 (11)
0011001101 -> 11 (11) Match! overshot skipping
0001000101 -> 8 (11)
0011000101 -> 9 (11)
0111000101 -> 10 (11)
1111000101 -> 11 (11) Match!
0000001001 -> 6 (11)
0000011001 -> 8 (11)
0000111001 -> 10 (11)
0001111001 -> 11 (11) Match! overshot skipping
0001011001 -> 9 (11)
0011011001 -> 10 (11)
0111011001 -> 11 (11) Match! overshot skipping
0001001001 -> 7 (11)
0011001001 -> 8 (11)
0111001001 -> 9 (11)
1111001001 -> 10 (11)
0001000001 -> 5 (11)
0011000001 -> 6 (11)
0111000001 -> 7 (11)
1111000001 -> 8 (11)
0000000100 -> 3 (11)
0000001100 -> 5 (11)
0000011100 -> 7 (11)
0000111100 -> 9 (11)
0001111100 -> 10 (11)
0011111100 -> 11 (11) Match! overshot skipping
0001011100 -> 8 (11)
0011011100 -> 9 (11)
0111011100 -> 10 (11)
1111011100 -> 11 (11) Match!
0001001100 -> 6 (11)
0011001100 -> 7 (11)
0111001100 -> 8 (11)
1111001100 -> 9 (11)
0001000100 -> 4 (11)
0011000100 -> 5 (11)
0111000100 -> 6 (11)
1111000100 -> 7 (11)
0000001000 -> 2 (11)
0000011000 -> 4 (11)
0000111000 -> 6 (11)
0001111000 -> 7 (11)
0011111000 -> 8 (11)
0111111000 -> 9 (11)
1111111000 -> 10 (11)
0001011000 -> 5 (11)
0011011000 -> 6 (11)
0111011000 -> 7 (11)
1111011000 -> 8 (11)
0001001000 -> 3 (11)
0011001000 -> 4 (11)
0111001000 -> 5 (11)
1111001000 -> 6 (11)
0001000000 -> 1 (11)
0011000000 -> 2 (11)
0111000000 -> 3 (11)
1111000000 -> 4 (11) end

Subsets found: 10
Subsets searched: 71
Subsets total number: 120

Процесс подсчёта количества пропущенных комбинаций кажется на столько не тривиальным, что почти невозможным. Вообще, как-то совсем медленно задача решается, то ли я тупой, то ли сама задача действительно на столько трудная... Осталось придумать как добавить пропуск недолётов. Вроде уже делал, тем не менее, с пропуском перелётов при поиске с повторами получился совершенно новый код. Пришлось изрядно напрячься и даже подебаггить, чтобы разобраться во всех нюансах. Основная сложность была в уникальной обработке первых повторяющихся элементов, будь они не ладны. Очень похожий код в совершенно разных случаях. С пропуском остальных повторяющихся элементов проще. Надеюсь, нигде скрытых ошибок и ляпов нет, потому что в коде, что я привёл перед этим есть весьма неприятная ошибка, хотя проявляется она весьма редко.