Combinatorial problem
How to write a function that will generate the next number, knowing the previous one. The sequence is like this:
0001 0010 0100 1000 0011 0101 0110 1001 1010 1100 0111 1011 1101 1110 1111
There are not necessarily 4 digits in a number.
4 answers
The problem is reduced to generating a sequence: 0, 1, 2, 3, 10, 20, 21, 30, 31, 32, 210, ... - it consists of all possible permutations, going in increasing order, such that each higher digit in the number is greater than the lower one. The first N (in our case, N = 4) let's match the power of two:0001 0010 0100 1000. The remaining elements will be the sum of the corresponding first elements (see which digits are included in the number from the auxiliary sequence and sum the corresponding digits. If N > 10, then for this scheme to work, when constructing the auxiliary sequence, you need to switch to the N-ric number system. It is possible that the binary representation of numbers from the auxiliary sequence really has something to do with Hamming codes - but I am not ready to bother with this right now :)
Here is the working code (in 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;
}
Somehow, this idea with arrays didn't appeal to me.. Here's what I got after 2 hours of sticking in the code:
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();
}
It seems to be working. But thank you all the same!!!
As for me, this is a normal shift to the right (then the number is provided in binary form) with an overflow check
Offset = 0; number = 0;
while( number != 0xF ){
new_number = ( number << 1 ) & 0xF;
if(new_number == 0) offset = offset << 1;
number = new_numer | offset;
print dec2bin(number);
}
Something like this ( in this case, 0xF because 4 numbers ) was written without checking, so that the algorithm would be more understandable.
Works on arbitrary-length bit strings
long getLastBitString(byte length){
return (1L << length + 1) - 1;
}
long getNextBitString(long in, byte length){
if(in == getLastBitString(length)) throw new IllegalArgumentException();
long left = in & in + 1;
long right = in ^ left;
return right + 1 | right >> 1 | left;
}
The total length of the sequence with the length of the string length will be (length + 1)*(length + 2)/2
For the sake of interest, I advise you to print the sequence for long lines in a column and pay attention to zeros.