java - 创建诗歌的所有可能排列

  显示原文与译文双语对照的内容
0 0

我的一个朋友写诗,他在它背后有一个非常特殊的节奏模式。 他所有的诗都有 4个栏,每个边都有 4行。 现在押韵模式是:


1
2
3
4

2
5
4
6

5
7
6
8

7
1
8
3

他问我有多少排列,如果我可以计算,但我不知道从哪里开始,我想不是最佳的解决方案。

( 编程语言最好是 java ( 脚本)/pseudo )

,Daniel

时间: 原作者:

0 0

请考虑创建一个诗的排列,紧密注意我们在方法上所做的选择。 首先,我们制作 8个类别,每一个有两个押韵行:


rhymes = {
 'A': ['fade', 'made'],
 'B': ['cow', 'how'],
 'C': ['can', 'fan'],
 'D': ['a', 'hey'],
 'E': ['answer', 'hampster'],
 'F': ['whiz', 'is'],
 'G': ['smut', 'what'],
 'H': ['key', 'we'],
 }

要创建一首诗,我们需要选择一个类别的排序。 给定押韵方案 [1,2,3,4,2,5,4,6,5,7,6,8,7,1,8,3],这可能是 ABCDBEDFEGFHGAHC 。 但它同样可以是 HGFEGDECDBCABHAF 。 有许多可能的排序,适合你的韵律方案。 总共有 8 ! = 8 *7*6*5*4*3*2*1 = 类别的40320排序。 在组合组合中,这称为 8项的排列数。

现在,一旦有了顺序,比如 ABCDBEDFEGFHGAHC,我们可以从类别 A 中选择一首诗,然后从类别中选择1 个可能项,等等。 有多少种方法可以做到这一点? 有 2个 ^8 = 256的方法使 8独立的二进制选择成为。 即使有 16行,在你做出前 8个选择之后,其余的"选项"被强制,因为每个类别只有一个选择。

所以总有


8! * 2**8 = 40320 * 256 = 10321920

或者超过 10的诗歌排列可能。


在 python 中,有些接近伪代码,你可以枚举这样的诗:


import itertools as IT

rhymes = [
 ['fade', 'made'],
 ['cow', 'how'],
 ['can', 'fan'],
 ['a', 'hey'],
 ['answer', 'hampster'],
 ['whiz', 'is'],
 ['smut', 'what'],
 ['key', 'we'],
 ]

scheme = [1,2,3,4,2,5,4,6,5,7,6,8,7,1,8,3]
# shift by 1 since Python uses 0-based indexing
scheme = [i-1 for i in scheme]

# 40320 itmes in orderings
orderings = IT.permutations(rhymes)

count = 0
for ordering in orderings:
 # 256 ways to select the lines given an ordering
 for lines in IT.product(*[IT.permutations(line)
 for line in ordering]):
 lines = map(iter, lines)
 for i in scheme:
 print(next(lines[i]))
 count += 1
 print

print(count)

这就产生了


fade
cow
can
a
how
answer
hey
whiz
hampster
smut
is
key
what
made
we
fan

原作者:
...