Some combination thing

combination.nim

import bitops


# for debugging a mask
# e.x.: 4 -> "0100"
func debug(mask: uint) =
  var str: string
  for i in countdown(63, 0):
    if mask.testBit i:
     str = str & "1"
    else:
      str = str & "0"
  debugEcho str

# turns a mask into a set of indicies
func toInd(mask: uint, n: uint): seq[uint] =
  for i in 0..n:
    if mask.testBit i:
      result.add uint i


func lastSetBit(mask: uint): int =
  # the whole countLeadingZeroBits thing can just be replaced with a for loop which is prob faster anyway
  # i just wanted to do this for fun
  if mask == 0'u:
    return 0
  else:
    63 - countLeadingZeroBits mask


func update(mask: uint, n: uint): uint =
  # cloning the mask to preserve wiped bits
  var bits = mask
  var pos = lastSetBit bits
  var counter = 0'u
  while uint(pos) >= n - 1 or mask.testBit(pos + 1):
    inc counter
    bits.clearBit(pos)
    pos = lastSetBit bits
  
  bits.clearBit pos
  for i in 0..counter:
    bits.setBit(pos + 1 + int i)

  #debug bits
  return bits
  

func combs(n: uint, m: uint): seq[seq[uint]] =
  result = @[]
  var mask = 0'u
  var inv = 0'u
  for i in 0..m-1:
    mask.setBit i
    inv.setBit(n - i - 1)

  result.add toInd(mask, n)

  while mask != inv:
    mask = update(mask, n)
    result.add toInd(mask, n)


echo combs(6, 3)
echo len combs(6, 3)
echo combs(6, 6)