【算法趣题】Q14 世界杯参赛国的国名接龙

引言

【算法趣题】是来自图灵程序设计丛书绝云译的《程序员的算法趣题》，书中是用Ruby实现的。这里是用python来实现。

问题描述

FIFA世界杯对足球爱好者而言是四年一次的盛事。下面我们拿2014年世界杯参赛国的国名做个词语接龙游戏。不过，这里用的不是中文，而是英文字母（忽略大小写）。下表是2014年FIFA世界杯的32个参赛国。

举个例子，如果像下面这样，那么连续3个国名之后接龙就结束了（因为没有英文名称以D开头的国家）。

Japan →→ Netherlands →→ Switzerland

假设每个国名只能使用一次，求能连得最长的顺序，以及相应的国名个数。

思路及python3实现

以D开头的国家存不存在，我们不知道，需要遍历国家列表，有没有简单的方式呢？我想到了字典，其中键是国家首字母，值就是对应的国家列表。如此有

country = ["Brazil", "Croatia", "Mexico", "Cameroon", "Spain", "Netherlands",

          "Chile", "Australia", "Colombia", "Greece", "Cote d'lvoire", "Japan",

          "Uruguay", "Costa Rica", "England", "Italy", "Switzerland", "Ecuador",

          "France", "Honduras", "Argentina", "Bosnia and Herzegovina", "Iran", "Nigeria",

          "Germany", "Portugal", "Ghana", "USA", "Belgium", "Algeria", "Russia", "Korea Republic"]

def initial_dict(country):

    country_dict = {} # 构造首字母国家字典

    for x in country:

        # 从字典country_dict中获取该国家x的首字母的值

        contry_list = country_dict.get(x[0])

        # 如果该首字母已有国家列表，即在原国家列表后添加该国

        if contry_list: 

            contry_list.append(x)

        # 如果该首字母还没有国家列表，即新增该国x为该首字母的国家列表

        else:

            contry_list = [x]

        # 重新赋值该首字母国家字典

        country_dict[x[0]] = contry_list 

    return country_dict 

接下来，我们就以Japan开头来推一下。

this_country = 'Japan'

country_list = ['Japan']

country_copy = country.copy()

country_copy.remove('Japan')

# 剔除Japan，剩下的国家形成字典

country_dict_one = initial_dict(country_copy)

如此，Japan的最后一个字母是n，查找N开头的值

next_list = country_dict_one.get(this_country[-1].upper())

这里N开头的国家有2个，所以有2种可能，因此要对这两种可能都要取一遍

先取next_one = 'Netherlands'，为了不妨碍下次去Nigeria，先做个copy

this_country_list = country_list.copy()

this_country_dict_one = country_dict_one.copy()

this_next_list = next_list.copy()

则Japan →→ Netherlands表示为

this_country_list.append(next_one)

然后在字典里移除Netherlands

this_next_list.remove(next_one) # N开头的国家列表里移除next_one

this_country_dict_one[this_country[-1].upper()] = this_next_list

然后重复以上操作，根据Netherlands的末尾字母s查找S开头的国家。

这样，可以以递归的形式封装函数了。

global order_list

order_list = [] # 国名接龙列表

def next_country(this_country, country_list, country_dict_one):  

    next_list = country_dict_one.get(this_country[-1].upper())

    if next_list:       

        for next_one in next_list:

            this_country_list = country_list.copy()

            this_country_dict_one = country_dict_one.copy()

            this_next_list = next_list.copy()

            this_country_list.append(next_one)

            this_next_list.remove(next_one)

            this_country_dict_one[this_country[-1].upper()] = this_next_list

            next_country(next_one, this_country_list, this_country_dict_one)           

    else:

        order_list.append(country_list)

        return 1

for x in country:# 遍历国家列表

    this_country = x

    country_list = [x]

    country_copy = country.copy()

    country_copy.remove(x)

    country_dict_one = initial_dict(country_copy)

    next_country(this_country, country_list, country_dict_one)

国名接龙列表为

国名接龙最长的国家数是

max_length = max([len(x) for x in order_list])

最后的结果即

result = list(filter(lambda x:len(x)==max_length,order_list))

即满足条件的解法有6种，最长的顺序为8，国家名的接龙如上所示。