标签: combinatorics

我试图在受边界条件约束的投资组合中生成所有可能的金融工具组合。

例如，假设我有一组列表，这些列表代表对投资组合的分配，受每种工具的总投资组合规模的最小和最大百分比影响：

"US Bonds" = {0.10,0.15,0.20,0.25,0.30}
"US Equities" = {0.25, 0.30, 0.35, 0.40, 0.45, 0.50}
"European Bonds" = {0.10, 0.15, 0.20}
"European Equities = {0.20,0.25,0.30,0.35,0.40,0.45,0.50}
 ...
"Cash" = {0.0, 0.05, 0.10, 0.15,...0.95}

我的资产清单如下所示：

[In]
Asset

[Out]
[[0.1, 0.15, 0.2, 0.25, 0.30],
[0.25, 0.30,0.35, 0.40, 0.45, 0.50],
[0.1, 0.15, 0.2],
[0.20, 0.25, 0.30,0.35, 0.40, 0.45, 0.50]
...
[0.0, 0.05, 0.1, 0.15, 0.2, 0.25,...0.95]]

在每种工具组合之和必须 = 1 的条件下，生成所有可能的投资组合的最有效方法是什么？

现在，我正在创建一个“投资组合”列表，如下所示：

portfolios  = [item for item in itertools.product(*asset) if  np.isclose(sum(item),1)]

（注意，'np.isclose' 负责处理时髦的 fp 算术）。 …

当要选择的元素数 (n) 为 5 并且选择的元素数 (r) 为 3 时，没有重复的组合如下所示：

0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4

随着 n 和 r 的增长，组合的数量很快就会变大。对于 (n,r) = (200,4)，组合数为 64684950。

使用 r 个嵌套的 for 循环迭代列表很容易，其中每个 for 循环的初始迭代值大于其嵌套的 for 循环的当前迭代值，如以下 jsfiddle 示例所示：https: // dotnetfiddle.net/wHWK5o

我想要的是一个根据其索引仅计算一种组合的函数。像这样的东西：

tuple combination(i,n,r) {
  return [combination with index i, when the number of elements to choose from is n …

考虑我有以下字典：

someDict = {
  'A': [1,2,3],
  'B': [4,5,6],
  'C': [7,8,9]
}

有没有一种简单的方法可以迭代为所有可能的组合创建新的字典，即？

{'A' : 1, 'B': 4, 'C':7}
{'A' : 1, 'B': 4, 'C':8}
{'A' : 1, 'B': 4, 'C':9}
{'A' : 2, 'B': 4, 'C':7}

ETC

假设我有一些列表列表，[[a, b], [c], [d, e, f], ...]其中列表中的列表可以是任意长度。我已经对列表进行了排序，使得最短的列表排在第一位，并且我想生成列表中所有元素组合的列表，以便我得到一个列表[[a, c, d, ...], [a, c, e, ...], [a, c, f, ...], [b, c, d, ...], ...]，即通过更改从最后一个列表中选取的元素来生成组合首先，向上移动列表以更改类似于计数的元素。

使用这个列表，我将使用列表的头部来使用惰性求值，因为我只需要 1 个满足谓词的列表。如何生成列表？

按键总是从“AIzaSy”开始（也​​许我错了，但我是这样）。接下来是 33 个字符。据我所知，他们使用字母、数字和一些特殊字符。每个字符位置大约有 64 个变体。大约有64^33 个组合（键）~ 401734511064747568885490523085290650630550748445698208825344 个键。

那么为什么他们选择恰好 39 (6+33) 个字符呢？

为什么不选择 20 个字符或 63 个字符？

我遇到了以下算法问题，该问题对运行时间有严格的限制（<10s并且没有大的内存占用），我被难住了。我的方法一半的测试用例都失败了。

问题

一个盒子包含许多物品，一次只能取出 1 个或 3 个。

盒子可以有多少种方式被清空？答案可能非常大，因此将其返回为 10^9+7 的模。

例如，最初有n=7个项目。可以通过九种方式删除它们，如下所示：

1.(1,1,1,1,1,1,1)
2.(1.1.1.1.3)
3.(1,1,1,3,1)
4.(1,1,3,1,1)
5.(1,3,1,1,1)
6.(3,1,1,1,1)
7.(1,3,3)
8.(3,1,3)
9.(3,3,1)

所以该函数应该返回 9。

函数描述：您的函数必须接受一个参数，n表示项目的数量，并返回一个整数，表示清空盒子的方式数。

限制条件：1<=n<=10^8

案例示例：

Input: 1
Sample OutPut: 1
Explanation: There is only 1 way to remove 1 item. Answer=(1%1000000007)=1

Input: 7
Sample OutPut: 9
There is only 9 ways to remove 7 items

我的方法

这导致了一个标准的递归关系，其中f(n) = f(n-3) + f(n-1)n > 2，所以我这样做如下

def memoized_number_of_ways(dic, n):
    if n not in dic:
        dic[n] = memoized_number_of_ways(dic, n-3) …

我有以下参考序列：

ref_seq      <- "MGHQQLYWSHPRKFGQGSRSCRVTSNRHGLIRKYGLNMSRQSFR"

和这个种子模式字符串：

seed_pattern <- "FKDHKHIDVKDRHRTRHLAK??????????"

该模式中有 10 个通配符 (?)。

鉴于此功能：

aa_count_normalized <- function(x) {
  AADict <- c(
    "A", "R", "N", "D", "C", "E", "Q", "G", "H",
    "I", "L", "K", "M", "F", "P", "S", "T", "W", "Y", "V"
  )
  AAC <- summary(factor(strsplit(x, split = "")[[1]], levels = AADict),
                 maxsum = 21
  ) / nchar(x)
  AAC
}

aa_count <- function(x) {
  AADict <- c(
    "A", "R", "N", "D", "C", "E", "Q", "G", "H",
    "I", "L", "K", "M", "F", "P", …

例如,

rank  permutation   
0     abc
1     acb
2     bac
3     bca
4     cab
5     cba

所以,如果有人要求我给排名4排列,答案就是出租车.请给出这个程序的java代码

有10个按钮.如果按正确顺序按下这些按钮可以解锁(按顺序按5次).按下每个按钮会触发解锁检查.

例如:"密码"是123456,我按下按钮0 1 2 3 4 5 6我从第6次按下按钮解锁.

我需要设计算法,以最有效的方式尝试所有可能的组合(即应按下最少量的按钮).

我可以将按钮编号按顺序解释为数字和按下按钮的数字作为数字位置,然后尝试所有99999组合以尝试解锁,但我觉得有更有效的算法可以做到这一点.

有什么我可以做的来优化这个搜索？

我正在做一些像下面这样的分词实验.

lst是一系列字符,output是所有可能的单词.

lst = ['a', 'b', 'c', 'd']

def foo(lst):
    ...
    return output

output = [['a', 'b', 'c', 'd'],
          ['ab', 'c', 'd'],
          ['a', 'bc', 'd'],
          ['a', 'b', 'cd'],
          ['ab', 'cd'],
          ['abc', 'd'],
          ['a', 'bcd'],
          ['abcd']]

我已经检查过combinations并permutations在itertools库中,
并尝试过组合学.
然而,似乎我在看错了,因为这不是纯粹的排列和组合......

似乎我可以通过使用大量循环来实现这一点,但效率可能很低.

编辑

单词顺序很重要,因此组合喜欢['ba', 'dc']或['cd', 'ab']无效.

订单应始终从左到右.

编辑

@Stuart的解决方案在Python 2.7.6中不起作用

编辑

@Stuart的解决方案在Python 2.7.6中有效,请参阅下面的注释.