标签: permutation

我需要一个算法,它返回一个字符串中所有字符的所有可能组合.

我试过了:

$langd = strlen($input);
 for($i = 0;$i < $langd; $i++){
     $tempStrang = NULL;
     $tempStrang .= substr($input, $i, 1);
  for($j = $i+1, $k=0; $k < $langd; $k++, $j++){
   if($j > $langd) $j = 0;
   $tempStrang .= substr($input, $j, 1);
 }
 $myarray[] = $tempStrang;
}

但是,它只返回与字符串长度相同的数量组合.

说$input = "hey",结果将是:hey, hye, eyh, ehy, yhe, yeh.

输入:包含从1到N的整数值的N个元素的只读数组(某些整数值可以出现多次!).和固定大小的存储区(10,100,1000等 - 不依赖于N).

如何在O(n)中判断数组是否代表一个排列？

-什么我实现了迄今(答案证明,这是不是好): -

给定表示置换原子的N个元素的数组,是否有类似的算法:

function getNthPermutation( $atoms, $permutation_index, $size )

其中$atoms是元素数组,$permutation_index是置换的索引,是置换$size的大小.

例如:

$atoms = array( 'A', 'B', 'C' );
// getting third permutation of 2 elements
$perm = getNthPermutation( $atoms, 3, 2 );

echo implode( ', ', $perm )."\n";

会打印:

B, A

没有计算每个排列直到$ permutation_index？

我听说过关于事实排列的一些事情,但我发现的每一个实现都会给出一个具有相同V大小的排列,这不是我的情况.

谢谢.

乍一看这个问题听起来很简单,但事实证明它看起来要复杂得多.这让我很难过.

有52c5 = 2,598,960种方法可以从52张牌中选择5张牌.然而,由于套装在扑克中是可以互换的,所以其中许多都是等同的 - 手2H 2C 3H 3S 4D相当于2D 2S 3D 3C 4H - 简单地换掉套装.根据维基百科,一旦你考虑到可能的套装重新着色,有134,459个不同的5张牌.

问题是,我们如何有效地生成所有这些可能的手？我不想生成所有的手,然后消除重复,因为我想将问题应用于更多的卡,以及评估快速螺旋失控的手的数量.我目前的尝试集中在生成深度优先,并跟踪当前生成的卡以确定哪些套装和等级对下一张卡有效,或者广度优先,生成所有可能的下一张卡,然后通过转换每个卡来删除重复通过重新着色来制作"规范"版本.这是我在Python中尝试广度优先的解决方案:

# A card is represented by an integer. The low 2 bits represent the suit, while
# the remainder represent the rank.
suits = 'CDHS'
ranks = '23456789TJQKA'

def make_canonical(hand):
  suit_map = [None] * 4
  next_suit = 0
  for i in range(len(hand)):
    suit = hand[i] & 3
    if suit_map[suit] is None:
      suit_map[suit] = next_suit
      next_suit += 1
    hand[i] = hand[i] & …

我想得到一个数字的所有组合,没有任何重复.如0.1.2,0.2.1,1.2.0,1.0.2,2.0.1,2.1.0.我试图找到一个简单的方案,但不能.我为它绘制了一个图形/树,这尖叫使用递归.但是如果可能的话,我想在没有递归的情况下这样做.

有人可以帮我这么做吗？

我正在研究Data.List模块中的代码,并不能完全围绕这种排列实现:

permutations            :: [a] -> [[a]]
permutations xs0        =  xs0 : perms xs0 []
  where
    perms []     _  = []
    perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is)
      where interleave    xs     r = let (_,zs) = interleave' id xs r in zs
            interleave' _ []     r = (ts, r)
            interleave' f (y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r
                                     in  (y:us, f (t:y:us) : zs)

有人可以详细解释这些嵌套函数如何相互连接/相互作用？

挑战

这是一项任务,灵感来自着名的英国电视游戏节目Countdown.即使不了解游戏,挑战也应该非常明确,但随时可以要求澄清.

如果你想看到这款游戏的动态片段,请查看此YouTube视频片段.它拥有1997年美妙的已故理查德怀特利.

您将获得6个数字,从集{1,2,3,4,5,6,8,9,10,25,50,75,100}中随机选择,以及100到999之间的随机目标数.目的是使用六个给定的数字和四个常用的算术运算(加法,减法,乘法,除法;遍及有理数)来生成目标 - 或尽可能接近任一侧.每个数字最多只能使用一次,而每个算术运算符可以使用任意次数(包括零).请注意,使用多少个数并不重要.

编写一个函数,它接受目标数和6个数字的集合(可以表示为列表/集合/数组/序列),并以任何标准数字符号(例如中缀,前缀,后缀)返回解决方案.该函数必须始终将最接近的结果返回给目标,并且必须在标准PC上运行最多1分钟.请注意,在存在多个解决方案的情况下,任何单个解决方案就足够了.

例子:

• {50,100,4,2,2,4},目标203,
  例如100*2 + 2 +(4/4)(精确),
  例如(100 + 50)*4*2 /(4 + 2)(精确)

• {25,4,9,2,3,10},目标465
  例如(25 + 10 - 4)*(9*2-3)(确切)

• {9,8,10,5,9,7},目标241
  例如((10 + 9)*9*7)+ 8)/ 5 (确切)

• {3,7,6,2,1,7},目标824
  例如((7*3)-1)*6-2)*7 (= 826;偏2)

规则

除了在问题陈述中提到的,没有进一步的限制.您可以使用任何标准语言编写函数(不需要标准I/O).一如既往的目标是用最少数量的代码来解决任务.

说,我可能不会简单地用最短的代码接受答案.我还将关注代码的优雅和算法的时间复杂度!

我的解决方案

当我找到空闲时间时,我正在尝试使用F#解决方案 - 当我有东西时会将它发布在这里!

格式

请以下列格式发布所有答案,以便于比较:

语言

字符数:???

完全混淆的功能:

(code here)

Run Code Online (Sandbox Code Playgroud)

清除(理想评论)功能:

(code here)

Run Code Online (Sandbox Code Playgroud)

关于算法/聪明的快捷方式的任何注释.

我有一些代码可以计算排列和组合,我正在努力让它更适合大数字.

我已经找到了一个更好的排列算法,避免了大的中间结果,但我仍然认为我可以做更好的组合.

到目前为止,我已经提出了一个特殊情况来反映nCr的对称性,但我仍然希望找到一种更好的算法来避免调用阶乘(r),这是一个不必要的大中间结果.如果没有这个优化,最后一次doctest尝试计算阶乘(99000)需要太长时间.

任何人都可以建议一种更有效的方法来计算组合？

from math import factorial

def product(iterable):
    prod = 1
    for n in iterable:
        prod *= n
    return prod

def npr(n, r):
    """
    Calculate the number of ordered permutations of r items taken from a
    population of size n.

    >>> npr(3, 2)
    6
    >>> npr(100, 20)
    1303995018204712451095685346159820800000
    """
    assert 0 <= r <= n
    return product(range(n - r + 1, n + 1))

def ncr(n, r):
    """
    Calculate the number of unordered combinations of r items taken …

我有数字,从0到8.我想在结果中,所有可能的那些数字组,每组应该使用所有数字,每个数字只能在一组中出现一次.

我想在PHP中看到可以打印出结果的解决方案.或者,至少,我想在组合学理论上有一些更新,因为我早就忘记了它.计算有多少排列的公式是什么？

示例集:

• 0-1-2-3-4-5-6-7-8
• 0-1-2-3-4-5-6-8-7
• 0-1-2-3-4-5-8-6-7
• 0-1-2-3-4-8-5-6-7
• 0-1-2-3-8-4-5-6-7
• 0-1-2-8-3-4-5-6-7
• 等等...

我需要帮助来实现一个允许生成建筑计划的算法,我最近在阅读Kostas Terzidis教授的最新出版物:排列设计:建筑,文本和上下文(2014)时偶然发现了这一点.

CONTEXT

• 考虑一个分为网格系统(a)的站点(b).
• 让我们考虑一个位于场地(c)范围内的空间列表和一个邻接矩阵来确定这些空间的放置条件和相邻关系(d)

引用Terzidis教授:

"解决这个问题的一种方法是随机地在网格中放置空格,直到所有空间都合适并且满足约束条件"

上图显示了这样的问题和样本解决方案(f).

算法(如书中简要描述)

1 /"每个空格都与一个列表相关联,该列表包含根据其所需邻域的程度排序的所有其他空格."

2 /"然后从列表中选择每个空间的每个单元,然后逐个放置在站点中,直到它们适合站点并满足相邻条件.(如果失败,则重复该过程)"

九个随机生成计划的示例:

我应该补充一点,作者后来解释说这个算法不依赖于暴力技术.

问题

如您所见,解释相对模糊,第2步相当不清楚(在编码方面).到目前为止我所有的都是"拼图":

• "网站"(所选整数列表)
• 邻接矩阵(嵌套列表)
• "空格"(列表字典)

每个单位:

• 返回其直接邻居的函数
• 它的理想邻居列表,其索引按排序顺序排列

• 基于其实际邻居的健康分数

  from random import shuffle
  
  n_col, n_row = 7, 5
  to_skip = [0, 1, 21, 22, 23, 24, 28, 29, 30, 31]
  site = [i for i in range(n_col * n_row) if i not in to_skip]
  fitness, grid = [[None if i in to_skip else [] for i in range(n_col * …

  Run Code Online (Sandbox Code Playgroud)