做有序排列的有效方式

-2

我不知道它是否可能，但我试图在C＃中找到一种算法，它可以生成一组数字的所有排列，其中有一些“空白空间”同时保持秩序。做有序排列的有效方式

实施例：

我有一个数组[1,2]和我需要所有所述有序排列有两个“空空间”。在这种情况下，我将有：

[1,2,null,null] 
[1,null,2,null] 
[1,null,null,2] 
[null,1,2,null] 
[null,1,null,2] 
[null,null,1,2]

我试图做包括置换前阵内所有的“空的空间”，但它产生太多的排列，我不需要。

在C＃中，函数可能是

private static List<int[]> PermutateWithSpace(this List<int> set, int numberOfEmptySpace) 
    { 
     // Algorithm which yield all possible permutations of my N "null" inside my set 
    }

来源

2017-06-06 KDelli

目前还不清楚算法的定义是什么。即什么决定了你有多少空的空间，它只是空荡荡的空间而已？在你的例子中'[1，null，null，2]'出现两次 - 为什么算法中的规则描述重复？ – LB2

如果可以的话，往上走一层。你可能不是为了好玩而这样做，而是因为其他一些算法需要它作为输入，对吧？有什么方法可以通过在读取输入时根据需要插入'null'来简单地制作出更聪明的人？至少保存订单应该更容易。 –

这是[数组排列]（https://stackoverflow.com/questions/2920315/permutation-of-array）中的答案，因为空值可以被视为重复字符。只是谷歌“重复生成排列”。 – Dukeling

当然，这算法很简单。

假设你有n个数字和m个空值。我们将从空值开始，然后插入数字。

我们做的第一件事是找出第一个数字在哪里。我们产生0,1,2，... m个零点，然后产生第一个数字。

假设我们在这个排列上得到了x个空值。现在我们计算出第二个数字的位置。我们产生0,1,2，... m-x个零点，然后产生第二个数字。

依此类推。

这是足够的提示，还是你需要看到算法写出来？

如果您遇到问题：

static IEnumerable<T> Append<T>(this IEnumerable<T> items, T item) 
{ 
    foreach(var i in items) 
     yield return i; 
    yield return item; 
} 

static IEnumerable<IEnumerable<int?>> DoIt(int min, int max, int nulls) 
{ 
    if (min > max) 
     yield return Enumerable.Repeat<int?>(null, nulls); 
    else 
     for(int i = 0; i <= nulls; ++i) 
      foreach(var r in DoIt(min + 1, max, nulls - i)) 
       yield return Enumerable.Repeat<int?>(null, i).Append(min).Concat(r);  
}

，或者甚至更紧凑，在LINQ风格！

static IEnumerable<IEnumerable<int?>> DoIt(int min, int max, int nulls) 
{ 
    return (min > max) ? 
     new[] { Enumerable.Repeat<int?>(null, nulls) } : 
     from i in Enumerable.Range(0, nulls + 1) 
     from r in DoIt(min + 1, max, nulls - i) 
     select Enumerable.Repeat<int?>(null, i).Append(min).Concat(r); 
}

来源

2017-06-06 14:21:44

谢谢！我会尝试用你的提示编写一个C＃算法。 – KDelli

工程就像一个魅力！令人难以置信的快速的方式 – KDelli

做有序排列的有效方式

回答

相关问题