标签: permutation

Python的itertools模块提供了许多关于使用生成器处理可迭代/迭代器的好东西.例如,

permutations(range(3)) --> 012 021 102 120 201 210

combinations('ABCD', 2) --> AB AC AD BC BD CD

[list(g) for k, g in groupby('AAAABBBCCD')] --> AAAA BBB CC D

Ruby中的等价物是什么？

相当于,我的意思是快速和内存效率(Python的itertools模块是用C编写的).

I encountered this problem when doing some enthusiastic programming. The problem can be expressed as follows:

For a multiset A, let P(A) denote the set of all possible permutations of A. P(A) is naturally divided into disjoint subsets that are equivalence classes, with the equivalence relation being "can be related by circular shifts." Enumerate all these equivalence classes by generating exactly one member from each of them.

例如,考虑多集{0,1,1,2}.排列"0112"和"1201"是唯一的排列,但后者可以通过对前者进行循环移位来找到,反之亦然.所需的算法不应生成两者.

当然,蛮力方法是可能的:只需生成排列 - 无论循环重复 - 使用任何多重排列算法,并丢弃与先前结果相比较的重复.然而,这在实践中往往效率低下.如果不是零记账,所需算法应该要求最少.

深刻理解对此问题的任何见解.

我有一套必须安排的产品.有P个产品,每个产品从1到P索引.每个产品可以安排到0到T的时间段.我需要构建满足以下约束的产品计划的所有排列:

If p1.Index > p2.Index then p1.Schedule >= p2.Schedule.

我正在努力构建迭代器.当产品数量是已知常量时,我​​知道如何通过LINQ执行此操作,但是当产品数量是输入参数时,我不确定如何生成此查询.

理想情况下,我想使用yield语法来构造此迭代器.

public class PotentialSchedule()
{
      public PotentialSchedule(int[] schedulePermutation)
      {
             _schedulePermutation = schedulePermutation;
      }
      private readonly int[] _schedulePermutation;
}


private int _numberProducts = ...;
public IEnumerator<PotentialSchedule> GetEnumerator()
{
     int[] permutation = new int[_numberProducts];
     //Generate all permutation combinations here -- how?
     yield return new PotentialSchedule(permutation);
}

编辑:_numberProducts = 2时的示例

public IEnumerable<PotentialSchedule> GetEnumerator()
{
    var query = from p1 in Enumerable.Range(0,T)
                from p2 in Enumerable.Range(p2,T)
                select new { P1 = p1, P2 = …

我遇到了问题,在网上找不到太多帮助.我需要从多个数字向量中找到数字的最小成本组合.所有向量的向量大小相同.例如,请考虑以下事项:

row [0]:  a  b  c  d   
row [1]:  e  f  g  h  
row [2]:  i  j  k  l  

现在我需要通过从每一行中取一个元素即矢量来找到数字的组合,例如:aei
在此之后,我需要找到彼此不相交的其他三个组合,例如:bfj,cgk,dhl.我根据选择的这四种组合计算成本.目标是找到能够降低成本的组合.另一种可能的组合可以是:afj,bei,chk,dgl.如果列的总数是d并且行是k,则可能的总组合是d ^ k.行存储为向量.我被困在这里,我发现很难为上述过程编写算法.如果有人能提供帮助我真的很感激.
谢谢.

// I am still working on the algorithm. I just have the vectors and the cost function.  

//Cost Function  , it also depends on the path chosen
float cost(int a, int b, PATH to_a) {  
float costValue;  
...  
...  
return costValue;  
}  

vector< vector < int > > row;  
//populate row  
...   
...
//Suppose  

//    row …

我试图找到给定字符串的排列,但我想使用迭代.我在网上找到的递归解决方案,我确实理解它,但将其转换为迭代解决方案实际上并没有成功.下面我附上了我的代码.我真的很感激帮助:

public static void combString(String s) {
    char[] a = new char[s.length()];
    //String temp = "";
    for(int i = 0; i < s.length(); i++) {
        a[i] = s.charAt(i);
    }
    for(int i = 0; i < s.length(); i++) {
        String temp = "" + a[i];    

        for(int j = 0; j < s.length();j++) {
            //int k = j;
            if(i != j) {
                System.out.println(j);
                temp += s.substring(0,j) + s.substring(j+1,s.length());
            }               
        }
        System.out.println(temp);
    }
}

假设您想以随机顺序迭代序列[0到n],只访问每个元素一次.有没有办法在O(1)内存中执行此操作,即不创建[1..n]序列std::iota并运行它std::random_shuffle？

某种迭代器以随机顺序吐出序列将是最佳的.

要求是应该可以通过选择另一个种子来获得另一个随机顺序.

假设我们给出一个载体foo,我们不得不暂时置换它(排序或重新排序的话),可以计算部分向量bar它的基础上,终于回到置换双方foo和bar对原有秩序foo-这意味着逆置换:

foo <- c(1, 7, 3, 5, 2)
o <- order(foo)
foo <- foo[o] # Now foo is permuted, and sorted: foo == 1 2 3 5 7
bar = 2 * foo # bar == 2 4 6 10 14

这里应该回答你的问题,以便我们得到以下所需的最终值:

foo == 1 7 3 5 2
bar == 2 14 6 10 4

这该怎么做？

请简单地回答:"你可以做bar = 2 * foo而不是置换它".这只是一个简单的例子.在某些情况下,我们必须foo对效率进行排序(快速搜索它)或类似的东西.

我看到这个问题是编程面试书,在这里我简化了问题.

假设你有一个A长度数组n,并且你也有一个P长度排列数组n.您的方法将返回一个数组,其中元素A将以指定索引的顺序出现P.

快速示例:您的方法需要A = [a, b, c, d, e]和P = [4, 3, 2, 0, 1].然后它会回来[e, d, c, a, b].您只能使用常量空间(即您不能分配另一个占用O(n)空间的数组).

想法？

我可以得到这样的整数排列:

myInt = 123456789

l = itertools.permutations(str(myInt))
[int(''.join(x)) for x in l]

有没有更有效的方法在Python中获取整数排列,省去了创建字符串的开销,然后加入生成的元组？对它进行定时,元组连接过程使这个时间长3倍 list(l).

增加了支持信息

myInt =123456789
def v1(i): #timeit gives 258ms
    l = itertools.permutations(str(i))
    return [int(''.join(x)) for x in l]

def v2(i): #timeit gives 48ms
    l = itertools.permutations(str(i))
    return list(l)

def v3(i): #timeit gives 106 ms
    l = itertools.permutations(str(i))
    return [''.join(x) for x in l]

这是一个经常被问到和回答的问题：如何在 Excel 中生成所有排列：

2011 2016 2017 2017 超级用户 2018 2021

现在到了2022 年，在它作为重复项关闭之前没有得到答案，这是不幸的，因为LAMBDA确实改变了这个问题的回答方式。

我很少有同样的需求，并且因不得不重新发明一个复杂的轮子而感到沮丧。因此，我将重新提出问题并在下面给出我自己的答案。我不会将任何提交标记为答案，但会邀请好的想法。我确信我自己的方法可以改进。

重申 2022 年问题

我正在尝试仅使用公式在 Excel 中创建循环。我想要实现的目标如下所述。假设我有 3 列作为输入： (i) 国家/地区；(ii) 变量；(iii) 年份。我想从这些输入进行扩展，然后为这些参数分配值。

输入：

输出：

如何使用 Excel 有效地做到这一点？

扩展 2018 年问题

我有三列，每一列都有不同类型的主数据，如下所示：

现在，我想要这三个单元格的所有可能组合 …