c# – 如何按最少到大多数非零元素的顺序迭代排列？

发布时间：2020-12-15 17:26:04 所属栏目：百科来源：网络整理

导读：我正在尝试编写一个C#函数,给定一个像new int [] {2,3,2}的参数,它指定每个元素的上限1,将返回以下内容(通过IEnumberable int [])： 0 0 00 0 10 1 00 2 01 0 00 1 10 2 11 0 11 1 01 2 01 1 11 2 1 请注意,顺序很重要：所有排列都包含0个非零元素,后跟所有

我正在尝试编写一个C#函数,给定一个像new int [] {2,3,2}的参数,它指定每个元素的上限1,将返回以下内容(通过IEnumberable< int []>)：

请注意,顺序很重要：所有排列都包含0个非零元素,后跟所有包含1个非零元素的排列等.在其中一个组中,顺序无关紧要.

我意识到这些在技术上可能不是排列,但它是我所知道的最接近的术语.另外我意识到一种方法是以某种顺序返回所有排列,然后根据计算有多少非零元素的函数对它们进行排序,但我希望有更优雅和高效的东西.

解决方法

我想要一个不首先计算所有内容然后排序的答案,同时仍然只经历最少量的事情.这就是我所拥有的.请注意,外部修改int []可能会搞砸结果(或者,可能会返回一个新的int []).

第一种方法告诉辅助方法它在输出中需要多少0.然后帮助程序计算结果,如果它不能填充足够的0或者它遍历所有数据则停止.

static IEnumerable<int[]> Permutation(int[] bounds)
{
  for(int num0s = bounds.Length; num0s >= 0; --num0s)
  {
    foreach(int[] ret in PermHelper(num0s,bounds,new int[bounds.Length]))
      yield return ret;
  }
}

static IEnumerable<int[]> PermHelper(int num0s,int index,int[] bounds,int[] result)
{
  //Last index.
  if(index == bounds.Length - 1)
  {
    if(num0s > 0)
    {
      result[index] = 0;
      yield return result;
    }
    else
    {
      for(int i = 1; i < bounds[index]; ++i)
      {
        result[index] = i;
        yield return result;
      }
    }
  }
  //Others.
  else
  {
    //still need more 0s.
    if(num0s > 0)
    {
      result[index] = 0;
      foreach(int[] perm in PermHelper(num0s - 1,index + 1,result))
        yield return perm;
    }
    //Make sure there are enough 0s left if this one isn't a 0.
    if(num0s < bounds.Length - index)
    {
      for(int i = 1; i < bounds[index]; ++i)
      {
        result[index] = i;
        foreach(int[] perm in PermHelper(num0s,result))
          yield return perm;
      }
    }
  }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!