2

Say we have the lexicographicaly integers 3,5,6,9,10,12 or 0011,0101,0110,1001,1010,1100 Each with two bits set.

What I want is to find the distance(how many lexicographical permutations between them, without doing the actuall permutations) between say 3 and 5 using as few operations as possible.

The distance table is as following

3->5  = 1 or 0011->0101 = 0001
3->6  = 2 or 0011->0110 = 0010
3->9  = 3 or 0011->1001 = 0011
3->10 = 4 or 0011->1010 = 0100
3->12 = 5 or 0011->1100 = 0101

So a function f(3,5) would return 1;

The function will always take arguments of same Hamming weight (same amount of set bits).

No arrays should be used.

Any idea would be great.

Edit

Forgot to mention, for any set bit size(the hamming weight) I will always use the first lexicographical permutation(base) as the first argument.

E.g. 

hamming weight 1 base = 1
hamming weight 2 base = 3
hamming weight 3 base = 7
...

Edit 2

The solution should work for any hamming weight, sorry I was not specific enough.

1-----1
  • 1,373
  • 8
  • 26

2 Answers2

5

Having a number
x = 2k1+2k2+...+2km
where k1<k2<...<km
it could be claimed that position of number x in lexicographically ordered sequence of all numbers with the same hamming weight is
lex_order(x) = C(k1,1)+C(k2,2)+...+C(km,m)
where C(n,m) = n!/m!/(n-m)! or 0 if m>n

Example:

3 = 20 + 21
lex_order(3) = C(0,1)+C(1,2) = 0+0 = 0

5 = 20 + 22
lex_order(5) = C(0,1)+C(2,2) = 0+1 = 1

6 = 21 + 22
lex_order(6) = C(1,1)+C(2,2) = 1+1 = 2

9 = 20 + 23
lex_order(9) = C(0,1)+C(3,2) = 0+3 = 3

Egor Skriptunoff
  • 23,359
  • 2
  • 34
  • 64
  • Would love to use this but, when m is 20 - 30, unfeasible to sort of calculate. – 1-----1 Nov 25 '12 at 22:32
  • @ks6g10 - All C(n,m) values for 1 – Egor Skriptunoff Nov 25 '12 at 23:17
  • @EgorSkriptunoff Then it comes to that I can not really use arrays. – 1-----1 Nov 25 '12 at 23:44
  • @ks6g10 - What constraints are there on your program? Are input number values limited by some constant? What amount of ROM size, RAM size and CPU time do you have at your disposal? My solution can be enhanced to require only O(log(x)) memory and O(log^2(x)) time for calculating lex_order(x). – Egor Skriptunoff Nov 26 '12 at 03:33
  • @EgorSkriptunoff I am doing the thing on the gpu and want to reduce the amount of memory reads, but I will investigate if this will have any good result. – 1-----1 Nov 26 '12 at 19:36
  • @EgorSkriptunoff Just wondering, is there a way of doing the reversed way, knowing the position and bit size, getting the integer set it represents? – 1-----1 Jan 05 '13 at 03:22
  • @ks6g10 - Yes, it is easy reversible if you have all C(n,m) precalculated and stored in a table. Firstly select maximum possible k_m, then k_(m-1) and so on. – Egor Skriptunoff Jan 29 '13 at 00:45
3

If a and b are the positions of the two set bits, with zero being the least significant position, and a always being greater than b, then you can calculate:

n = a*(a-1)/2 + b

and the distance between two values is the difference between the two n values.

Example:

3->12:
  3:  a1=1, b1=0, n1=0
  12: a2=3, b2=2, n2=5
  answer: n2-n1 = 5

To extend this to other hamming weights, you can use this formula:

n = sum{i=1..m}(factorial(position[i])/(factorial(i)*factorial(position[i]-i)))

where m is the hamming weight, and position[i] is the position of the i'th set bit, counting from the least significant bit, with the least significant set bit's position being position[1].

Vaughn Cato
  • 63,448
  • 5
  • 82
  • 132