How to write a function that will generate the next number, knowing the previous one. The sequence is:

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

Numbers in the number are not necessarily 4

  • Upd: judging by Google, it is somehow connected with comrade. Hemming. But I, unfortunately, do not know how = ( - Tim Rudnevsky

4 answers 4

The task is reduced to the generation of a sequence: 0, 1, 2, 3, 10, 20, 21, 30, 31, 32, 210, ... - it consists of all possible permutations going in ascending order, such that each highest digit in the number more younger. The first N (in our case N = 4) we assign the degree of two to the correspondence: 0001 0010 0100 1000 . The remaining elements will be the sum of the corresponding first elements (we look at which numbers are included in the number from the auxiliary sequence and sum up the corresponding figures. If N> 10, then, in order for this scheme to work, when building the auxiliary sequence, you need to go to the N-rhythmic number system. that the binary representation of numbers from the auxiliary sequence is really somehow connected with Hamming codes - but this is not ready for bothering 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, after all, this idea with arrays did not attract me .. Here's what happened after 2 hours of sticking into 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 still thank you all !!!

    As for me - this is the usual 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) wrote without checking that the algorithm was more understandable.

    • incorrect. Although the attempt is good. - gecube

    Works on bit strings of arbitrary length

     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 equal to (length + 1)*(length + 2)/2

    For the sake of interest, I advise you to print a sequence for long rows in a column and pay attention to the zeros.

    • Not on assignment. Your code prints 0001 0010 0011 0101 0110 0111 1011 1101 ... In short, not that. - Tim Rudnevsky