Как сгенерировать варианты всех возможных перестановок, идущих в возрастающем порядке?

Рейтинг: 0Ответов: 2Опубликовано: 07.05.2011

Как написать функцию, которая будет генерировать следующее число, зная предыдущее. Последовательность вот такая:

0001 0010 0100 1000 0011 0101 0110 1001 1010 1100 0111 1011 1101 1110 1111

Цифр в числе не обязательно 4.

алгоритм комбинаторика
Источник: Stack Overflow на русском

Ответы

▲ 1Принят

Как-то всё-таки эта идея с массивами меня не привлекла.. Вот, что получилось у меня через 2 часа втыкания в код:

typedef unsigned int UINT;

int count(UINT v){
    v = (v & 0x55) + ((v >> 1) & 0x55);
    v = (v & 0x33) + ((v >> 2) & 0x33);
    return (v & 0x0f) + ((v >> 4) & 0x0f);
}

void main()
{
    UINT digitsCount=4;
    UINT mask=0xF;
    for(UINT digits=1;digits<=digitsCount;++digits){
        UINT number=pow(2.,(double)digits)-1;
        do{
            cout<<number<<" ";
            UINT rightOneMask=number&(-number);   // Указывает на крайнюю правую единицу
            while (((rightOneMask<<1)&number)!=0){  // Указывает на крайнюю правую единицу, которую можно сдвинуть
                rightOneMask=rightOneMask<<1;
            }
            if (((rightOneMask<<1)&mask)==0) // если вышли за пределы числа
                break;
            number=number&(~rightOneMask);
            number=number|(rightOneMask<<1);
            UINT hNum=number&((rightOneMask&-rightOneMask)-1);
            number=number&~((rightOneMask&-rightOneMask)-1);
            int c=count(hNum);
            number+=pow(2.,(double)c)-1;
        }
        while(1);
    }

    cout<<endl<<endl;

    _getch();
}

Вроде бы работает. Но всё равно всем спасибо!!!

▲ 4

Задача сводится к генерации последовательности: 0, 1, 2, 3, 10, 20, 21, 30, 31, 32, 210, ... - она состоит из всех возможных перестановок, идущих в возрастающем порядке, таких что каждая старшая цифра в числе больше младшей. Первым N (в нашем случае N = 4) поставим в соответствие степени двойки:0001 0010 0100 1000. Остальные элементы будут являться суммой соответствующих первых элементов (смотрим, какие цифры входят в число из вспомогательной последовательности и суммируем соответствующие цифры. Если N > 10, то, чтобы эта схема работала, при построении вспомогательной последовательности нужно перейти к N-ричной системе счисления. Возможно, что двоичное представление чисел из вспомогательной последовательности действительно как-то связанно с кодами Хемминга - но этим заморачиваться сейчас не готов :)

Вот работающий код (на C#): 

        const int digitCount = 4;

        int[] GetNextIndexArray(int[] indexArray)
        {
            int[] newIndexArray = new int[0];
            int length = indexArray.Length;

            for (int i = 0; i < length; i++)
            {
                if ((i == length - 1 || indexArray[i] + 1 < indexArray[i + 1]) && 
                    indexArray[i] < digitCount - 1)
                {
                    newIndexArray = new int[length];
                    Array.Copy(indexArray, newIndexArray, length);
                    newIndexArray[i]++;

                    for (int j = 0; j < i; j++)
                    {
                        newIndexArray[j] = j;
                    }

                    break;
                }
                else if (i == length - 1 && indexArray[i] >= digitCount - 1)
                {
                    newIndexArray = new int[length + 1];
                    for (int j = 0; j <= length; j++)
                    {
                        newIndexArray[j] = j;
                    }

                    break;
                }
            }

            return newIndexArray;
        }

        int GetNext(int n)
        {
            List<int> indexArray = new List<int>();

            for (int i = 0; i < digitCount; i++)
            {
                if ((n & (int)Math.Pow(2, i)) != 0)
                {
                    indexArray.Add(i);
                }                
            }

            int[] newIndexArray = GetNextIndexArray(indexArray.ToArray());
            int result = 0;

            foreach (int index in newIndexArray)
            {
                result += (int)Math.Pow(2, index);
            }

            return result;
        }