Integer factorization and combination in C#

 
     F
R = --- 
     D 

When transmitting data in a certain rate ( R ), clock rate ( F ) has to be divided ( D ). And sometimes, it is desirable to have the rate as integer. Usually, F is given from the transmitting device. And we want to know every possible R.

This asks R to be integer and asks D to divide F without fraction. Then F has to be integer multiple of D. First F has to be factored into prime numbers. Then all the permutation of prime numbers has to be generated. Then each permuation can be D ( or R in here).

Prime numbers of clock can be calculated on the fly but not the point in this article. Assume prime numbers are already known like { 2, 3, 5, 7, 11, ... }. Then factors of R can be enumerated by continuously divide with each primes like below function.

IEnumerable< int> Factors(int n, IEnumerable< int> primes)
{
  foreach (int p in primes) {
    if (p * p > n) break;

    while (n % p == 0) {
      yield return p;
      n /= p;
    }
  }

  if (n > 1) yield return n;
}

Then each factors can be permuted and enumerated so that each dividible product can be calculated.

IEnumerable< int[]> Combination(Tuple< int, int>[] groups )
{
  var product = new int[groups.Count()];
  foreach (var p in RecursivelyCombine(product, groups, 0)) {
    yield return p;
  }
}

IEnumerable< int[]> RecursivelyCombine(int[] products, Tuple< int, int>[] factors, int index)
{
  var factor = factors[index];
  for (int i = 0; i <= factor.Item2; ++i) {
    products[index] = i;
    if (index == factors.Length - 1) {
      yield return products;
    }
    else {
      foreach (var p in EnumerateProduct(products, factors, index + 1)) {
        yield return p;
      }
    }
  }
  yield break;
}

Then here is function that enumerate all possible rates with a given clock F.

IEnumerable< int> Rates(int F) // F = 50
{
  auto factors = Factors( 500, new int [] {  2, 3, 5, 7 } );
  // factors = { 2, 2, 5, 5, 5 }
    
  var groups = factors.GroupBy(f => f).Select(g => new Tuple(g.Key, g.Count())).ToArray();
  // groups = { {2,2}, {5,3} }  <- 2^2 x 5^3

  foreach (int[] pm in Combination(groups)) { // {0,0}, {0,1}, {0,2}, {0,3}, {1,0}, .... , {2,3}

    // pm can be { 1, 2 } which means D = 2^1 x 5^2
    int D = 1;
    for (int i = 0; i < groups.Length; ++i) {
      D *= (int)Math.Pow(groups[i].Item1, pm[i]);
    }

    yield return D;
  }
}