文件 1 包含需要随机配对的单词列表
Tiger
Cat
Fish
Frog
Dog
Mouse
Elephant
Monkey
文件 2 包含随机配对期间不应使用的对(在任何解决方案中)。
Elephant-Dog
Cat-Fish
Monkey-Frog
狗象、鱼猫、青蛙猴子也应该被删除,因为它们的对出现在 File2 中(无论方向如何)我总共需要 6 个解决方案,并且在每个解决方案中,最多应该有 5 对。 Tiger-Cat 和 Cat-Tiger 应视为相同,如果它们同时出现在任何解决方案中,则应将其删除。同一对(例如青蛙-狗)可以出现在许多解决方案中。
输出看起来像(这里只给出了一种解决方案)
Tiger-Cat
Cat-Dog
Monkey-Cat
Frog-Dog
Elephant-Cat
答案1
bash
解决方案:
for i in {1..6}; do
printf '==== solution %d ====\n' "$i"
# initialize solution
solution=()
while [ ${#solution[@]} -lt 5 ]; do
# select two random lines from file1
w1=$(shuf -n 1 file1)
w2=$(shuf -n 1 file1)
# skip if word1 is the same as word2
[ "$w1" == "$w2" ] && continue
# skip if pair exists in same solution or is not allowed from file2
cat <(printf '%s\n' "${solution[@]}") file2 | grep -qx "$w1-$w2" && continue
cat <(printf '%s\n' "${solution[@]}") file2 | grep -qx "$w2-$w1" && continue
# output
solution+=("${w1}-${w2}")
done
printf '%s\n' "${solution[@]}"
done
输出:
==== solution 1 ====
Fish-Monkey
Elephant-Mouse
Dog-Tiger
Mouse-Fish
Dog-Cat
==== solution 2 ====
Cat-Frog
Elephant-Monkey
Cat-Mouse
Tiger-Elephant
Fish-Tiger
==== solution 3 ====
Cat-Frog
Tiger-Monkey
Frog-Elephant
Dog-Fish
Elephant-Cat
==== solution 4 ====
Cat-Dog
Mouse-Elephant
Monkey-Elephant
Cat-Monkey
Tiger-Cat
==== solution 5 ====
Tiger-Monkey
Tiger-Cat
Mouse-Monkey
Mouse-Fish
Monkey-Cat
==== solution 6 ====
Monkey-Mouse
Dog-Monkey
Monkey-Fish
Tiger-Elephant
Cat-Tiger
答案2
Perl 解决方案。
#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };
use List::Util qw{ shuffle };
open my $fh_list, '<', shift or die $!;
chomp( my @words = sort <$fh_list> );
open my $fh_ban, '<', shift or die $!;
my %ban;
while (<$fh_ban>) {
chomp;
my ($ban1, $ban2) = sort split /-/;
undef $ban{"$ban1-$ban2"};
}
my @all;
for my $i1 (0 .. $#words) {
for my $i2 ($i1 + 1 .. $#words) {
my $pair = [ $i1, $i2 ];
push @all, $pair unless exists $ban{"$words[$i1]-$words[$i2]"};
}
}
my @solutions;
my %used;
while (@solutions < 6) {
my $solution = join ' ', sort +(shuffle(0 .. $#all))[0 .. 4];
redo if exists $used{$solution};
undef $used{$solution};
push @solutions, [
map join('-', @words[
@{ $all[$_] }[int rand 2 ? (0, 1) : (1, 0)]
]), split ' ', $solution
];
}
say join "\n", @$_, '---' for @solutions;
它首先将单词读入数组,并将禁止的词对读入哈希。然后,它生成所有可能的组合,其中第一个元素排序在第二个元素之前。然后它会打乱所有可能的对并选择前五个,直到有 6 个不同的解决方案。 “@all”数组仅包含元素的索引,并且在输出相应元素时随机打乱它们,因此您可以同时获得“Cat-Dog”和“Dog-Cat”。
输出示例:
Elephant-Cat
Monkey-Cat
Fish-Elephant
Monkey-Fish
Frog-Tiger
---
Tiger-Cat
Tiger-Fish
Fish-Elephant
Dog-Monkey
Cat-Frog
---
Tiger-Fish
Cat-Elephant
Elephant-Frog
Mouse-Elephant
Frog-Cat
---
Tiger-Fish
Mouse-Fish
Monkey-Fish
Frog-Tiger
Cat-Dog
---
Dog-Frog
Elephant-Frog
Dog-Tiger
Tiger-Mouse
Tiger-Monkey
---
Tiger-Cat
Elephant-Frog
Tiger-Mouse
Cat-Frog
Cat-Dog
---