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

Question

我的一个朋友写诗，他有一个非常特殊的节奏模式。他所有的诗都有 4 个五线谱，每个五线谱有 4 行。所以押韵模式现在是这样的：

1
2
3
4

2
5
4
6

5
7
6
8

7
1
8
3

他问我有多少排列，我是否可以全部计算出来，但我真的不知道从哪里开始，除了蛮力，我猜这不是最佳解决方案。

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

干杯，丹尼尔

Answer 1

因为每种押韵类型恰好出现两次和 2！= 2 假设行不相等，您有 2^8 = 256 种可能性

Answer 2

Consider what it takes to create a poem-permutation, paying close attention to the choices we have to make along the way. First, we make 8 categories, with two rhyming lines (or words) in each:

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'],
    }

To create a poem, we need to pick an ordering of the categories. Given the rhyming scheme [1,2,3,4,2,5,4,6,5,7,6,8,7,1,8,3], that could be ABCDBEDFEGFHGAHC. But it could equally well be HGFEGDECDBCABHAF. There are many possible orderings for the categories which fit your rhyming scheme. In total there are 8! = 8*7*6*5*4*3*2*1 = 40320 orderings for the categories. In combinatorics this is called the number of permutations of 8 items.

Now once we have an ordering, such as ABCDBEDFEGFHGAHC, we can construct a poem by selecting 1 of the 2 possible items from category A, then 1 of the 2 possible items from category B, and so on. How many ways are there to do this? Well there are 2^8 = 256 ways to make 8 independent binary choices. Even though there are 16 lines, after you make the first 8 choices, the rest of the "choices" are forced since there is only one choice left for each category.

So in total there are

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

or a little over 10 million poem-permutations possible.

---

In Python, which is somewhat close to pseudocode, you could enumerate the poems like this:

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)

which yields, for example,

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

Answer 3

因为有 8 种线 1 2 3 4 5 6 7 8

第一个五线谱的种类数是 8*7*6*5 = 1680

第二五线谱可以是 1*4*1*3 = 12

第三五线谱可以是 1*2*1*1 = 2

第 4 次保存可以是 1*1*1*1 = 1

所以可能性的总数是 1680*12*2*1 = 40320