标签: permutation

我有一组排列,我想删除同构排列.

我们有多S组排列,其中每组包含K排列,每个排列表示为N元素和数组.我目前正在将其保存为数组int pset[S][K][N],其中S,K并且N是固定的,并且N大于K.

两组排列,A并且B,如果存在排列,则是同构的,P将元素转换A为B(例如,if a是元素的集合A,然后P(a)是集合的元素B).在这种情况下,我们可以说P制造A和B同构.

我目前的算法是:

1. 我们选择所有对s1 = pset[i]和s2 = pset[j],使得i < j
2. 从choosen集(每个元素s1和s2)从numered 1到K.这意味着每个元素都可以表示为s1[i]或s2[i],在哪里0 < i < K+1
3. 对于每一个排列T的K …

我试图使用itertools.permutations()来返回字符串的所有排列,并仅返回作为一组单词成员的那些排列.

import itertools

def permutations_in_dict(string, words): 
    '''
    Parameters
    ----------
    string : {str}
    words : {set}

    Returns
    -------
    list : {list} of {str}    

    Example
    -------
    >>> permutations_in_dict('act', {'cat', 'rat', 'dog', 'act'})
    ['act', 'cat']
    '''

我目前的解决方案在终端上运行良好,但不知何故无法通过测试用例...

return list(set([''.join(p) for p in itertools.permutations(string)]) & words)

任何帮助将不胜感激.

我有一个日历，通常是一个包含多行的 csv 文件。每行对应一个个体，是一个连续值“0”和“1”的序列，其中“0”表示空时隙，“1”表示占用时隙。一行中不能有两个分隔的序列（例如，两个由“0”分隔的“1”序列，例如“1,1,1,0,1,1,1,1”）。

问题是通过组合个体并解决时隙之间的冲突来最小化行数。注意时隙不能重叠。例如，对于 4 个个体，我们有以下序列：

id1:1,1,1,0,0,0,0,0,0,0
id2:0,0,0,0,0,0,1,1,1,1
id3:0,0,0,0,1,0,0,0,0,0
id4:1,1,1,1,0,0,0,0,0,0

可以将它们排列成两行，同时跟踪排列的个人（记录）。在我们的例子中，它产生：

1,1,1,0,1,0,1,1,1,1 (id1 + id2 + id3)
1,1,1,1,0,0,0,0,0,0 (id4)

约束条件如下：

1. 人数从500到1000不等，
2. 序列的长度永远不会超过30
3. 文件中的每个序列都具有完全相同的长度，
4. 算法需要在执行时间上合理，因为这个任务最多可能重复 200 次。
5. 我们不需要寻找最优解，一个接近最优的解就足够了。
6. 我们需要跟踪组合的个体（如上例所示）

遗传算法似乎是一个不错的选择，但它如何随着这个问题的规模（在执行时间方面）扩展？

Matlab或R 中的建议将（非常）感谢。

这是一个示例测试：

id1:1,1,1,0,0,0,0,0,0,0
id2:0,0,0,0,0,0,1,1,1,1
id3:0,0,0,0,1,0,0,0,0,0
id4:1,1,1,1,1,0,0,0,0,0
id5:0,1,1,1,0,0,0,0,0,0
id6:0,0,0,0,0,0,0,1,1,1
id7:0,0,0,0,1,1,1,0,0,0
id8:1,1,1,1,0,0,0,0,0,0
id9:1,1,0,0,0,0,0,0,0,0
id10:0,0,0,0,0,0,1,1,0,0
id11:0,0,0,0,1,0,0,0,0,0
id12:0,1,1,1,0,0,0,0,0,0
id13:0,0,0,1,1,1,0,0,0,0
id14:0,0,0,0,0,0,0,0,0,1
id15:0,0,0,0,1,1,1,1,1,1
id16:1,1,1,1,1,1,1,1,0,0

解决方案

@Nuclearman 提供了一个基于贪婪算法的工作解决方案O(NT)（其中N是个体（id）T的数量，是时隙（列）的数量）。

我正在寻找一种算法,它将采用数字或单词并找到它们的所有可能变体,并让我定义要一起查找的值.

示例假设字符串或数组是:

cat  
dog  
fish  

那么值为2的结果可能是:

cat dog  
cat fish  
dog cat  
dog fish  
fish cat  
fish dog   

因此,3个项目的结果是6个可能的变化,2个结果匹配
3个结果匹配它将是:

cat dog fish  
cat fish dog  
dog cat fish  
dog fish cat  
fish cat dog  
fish dog cat  

...甚至可能有更多的选择

我在这个例子的Stackoverflow上找到了一个链接来做这个,但它是在javascript中,我想知道是否有人知道如何在PHP中执行此操作可能已经构建了一些东西？

http://www.merriampark.com/comb.htm(死链接)

我想要洗牌一系列独特的项目,但不要做一个完全随机的洗牌.我需要确保混洗列表中的元素与原始列表中的位置不同.因此,如果原始列表是(A,B,C,D,E),这个结果就可以了:(C,D,B,E,A),但这个不会:( C,E,A, D,B)因为"D"仍然是第四项.该列表最多包含七个项目.极端效率不是一个考虑因素.我认为这对Fisher/Yates的修改可以解决问题,但我不能用数学方法证明:

function shuffle(data) {
    for (var i = 0; i < data.length - 1; i++) {
        var j = i + 1 + Math.floor(Math.random() * (data.length - i - 1));

        var temp = data[j];
        data[j] = data[i];
        data[i] = temp;
    }
}

我正在对排名算法进行一些研究,并且想要给出排序列表和该列表的一些排列,计算两个排列之间的一些距离.对于Levenshtein距离的情况,这对应于计算序列与该序列的分类副本之间的距离.例如,还有"反转距离",这里详细描述了线性时间算法,我正在努力实现.

有没有人知道反演距离的现有python实现,和/或Levenshtein距离的优化？我在大约50,000到200,000个元素的序列上计算它,因此O(n ^ 2)太慢,但O(n log(n))或更好应该足够.

还可以理解排列相似性的其他度量.

为未来的人们编辑:

基于Raymond Hettinger的回应 ; 它不是Levenshtein或反转距离,而是"格式塔模式匹配":P

from difflib import SequenceMatcher
import random
ratings = [random.gauss(1200, 200) for i in range(100000)]
SequenceMatcher(None, ratings, sorted(ratings)).ratio()

在可怕的桌面上运行约6秒钟.

编辑2:如果你可以将你的序列强制转换为[1 .. n]的排列,那么曼哈顿度量的变化非常快并且有一些有趣的结果.

manhattan = lambda l: sum(abs(a - i) for i, a in enumerate(l)) / (0.5 * len(l) ** 2)
rankings = list(range(100000))
random.shuffle(rankings)
manhattan(rankings) # ~ 0.6665, < 1 second

归一化因子在技术上是近似值; 它对于偶数大小的列表是正确的,但应该(0.5 * (len(l) ** 2 - 1))用于奇数大小的列表.

Edit3:还有其他几种算法可用于检查列表相似度!的肯德尔头排名系数和斯皮尔曼 …

这是一个面试问题,我没有在stackoverflow或外部找到任何令人满意的答案.问题陈述:

给定算术表达式,删除多余的括号.例如((a*b)+ c)应该变成a*b + c

我可以想到一种将中缀表达式转换为后置修复并将其转换回中缀的明显方法 - 但是有更好的方法吗？

我正在写一些问答游戏,如果玩家未能解决问题,需要计算机在测验中解决1个游戏.

鉴于数据:

1. 要使用的6个号码的列表,例如4,8,6,2,15,50.
2. 目标值,其中0 <值<1000,例如590.
3. 可用的操作是除法,加法,乘法和除法.
4. 可以使用括号.

生成数学表达式,其中评估与目标值相等或尽可能接近.例如,对于上面给出的数字,表达式可以是:(6 + 4)*50 + 15*(8-2)= 590

我的算法如下:

1. 从上面的(1)生成给定数字的所有子集的所有排列
2. 对于每个排列,生成所有括号和运算符组合
3. 算法运行时跟踪最接近的值

我想不出上面的蛮力算法的任何智能优化,这将使其加速数量级.此外,我必须优化最坏的情况,因为许多测验游戏将在服务器上同时运行.

今天为解决这个问题而编写的代码是(从项目中提取的相关内容):

from operator import add, sub, mul, div
import itertools


ops = ['+', '-', '/', '*']
op_map = {'+': add, '-': sub, '/': div, '*': mul}

# iterate over 1 permutation and generates parentheses and operator combinations
def iter_combinations(seq):
    if len(seq) == 1:
        yield seq[0], str(seq[0])
    else:
        for i in range(len(seq)):
            left, right = seq[:i], seq[i:]  # split input list at i`th …

我想按字典顺序打印字符串的所有排列.我写这段代码:

void permute(char *a, int i, int n) {
   if (i == (n-1)) printf("\"%s\"\n", a);
   else {
       for (int j = i; j < n; j++) {
           swap((a+i), (a+j));
           permute(a, i+1, n);
           swap((a+i), (a+j));
       }
   }
}

我有例如字符串abc,所以我希望按照左栏中的字典顺序接收所有排列,但我的结果与右列相同.

"abc"                   "abc"
"acb"                   "acb"
"bac"                   "bac"
"bca"                   "bca"
"cab"            <
"cba"                   "cba"
                 >      "cab"

有人可以帮我弄这个吗？我看到了一些算法,但看起来很难.我想我可以在数组中保存所有生成的字符串然后对这个数组进行排序,但是我不能写这个(我是C语言的初学者).

给定一个arr大小的数组n,并且索引0<=i<n!我想返回第i个排列.

我能够编写一个获取所有排列的方法:

function permute (arr) {
  var permutations = [];
  if (arr.length === 1) {
    return [ arr ];
  }

  for (var i = 0; i <  arr.length; i++) { 
    var subPerms = permute(arr.slice(0, i).concat(arr.slice(i + 1)));
    for (var j = 0; j < subPerms.length; j++) {
      subPerms[j].unshift(arr[i]);
      permutations.push(subPerms[j]);
    }
  }
  return permutations;
}

如何修剪它只获得递归的一个分支？