Vin*_*aba 6 string algorithm graph
例:
n = 9
words = {Bike, Tire, Fuel, Biker, Filter, Trike}
output = {B,T,I,K,E,F,U,L,R}
(输出顺序并不重要.需要注意的是,给定像FOO这样的单词,不能使用F,O作为字母表,但总是需要F,O,O.类似的字母表分别处理)
解决这个问题最有效的算法是什么？
我正在考虑使用每个角色的频率,但这似乎没有多大帮助.
编辑：这是针对编辑的问题进行更新的。详细信息请参阅修订历史记录。
根据评论，人们必须假设（或至少考虑可能性）这实际上是一个 NP 完全问题。因此，在有人证明或反驳这个问题的实际复杂性之前，这里有一个暴力解决方案，至少应该计算出正确的输出。
编辑2.0：正如shapiro.yaacov 在他的回答中指出的那样，它确实是 NP 完全的
它使用一些实用程序类来计算所有单词的初始集合中一定数量的字母的所有组合。由于存在字母n^k组合k（给定初始字母集n），这显然在多项式时间解决方案的意义上不是“有效”的 - 但目前尚不清楚这样的解决方案是否存在。
为了根据编辑的问题中提到的点验证输出（即字母必须在结果列表中出现的频率与单词中出现的频率相同），我使用了一个示例输入，其中包含重复字母的单词：
"BIKE", "BIKER", "TRIKE", "BEER", DEER", "SEED", "FEED"
对于这个输入，程序打印
0 letters: [], created words: []
1 letters: [B], created words: []
2 letters: [B, B], created words: []
3 letters: [B, B, B], created words: []
4 letters: [B, E, E, R], created words: [BEER]
5 letters: [B, D, E, E, R], created words: [BEER, DEER]
6 letters: [B, D, E, E, F, R], created words: [BEER, DEER, FEED]
7 letters: [B, D, E, E, F, R, S], created words: [BEER, DEER, SEED, FEED]
8 letters: [B, D, E, E, F, I, K, R], created words: [BIKE, BIKER, BEER, DEER, FEED]
也许它可以被认为是有帮助的，也许可以作为其他人的起点或构建块。
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.TreeSet;
public class MaximizeWords
{
public static void main(String[] args)
{
List<String> words = Arrays.asList(
"BIKE",
"BIKER",
"TRIKE",
"BEER",
"DEER",
"SEED",
"FEED"
);
List<Character> allLetters =
new ArrayList<Character>(allLettersOf(words));
for (int n=0; n<=8; n++)
{
CombinationIterable<Character> combinations =
new CombinationIterable<Character>(n, allLetters);
List<Solution> solutions = new ArrayList<Solution>();
for (List<Character> combination : combinations)
{
Collections.sort(combination);
Solution solution = new Solution(words, combination);
solutions.add(solution);
}
Solution bestSolution = Collections.max(solutions,
new Comparator<Solution>()
{
@Override
public int compare(Solution s0, Solution s1)
{
return Integer.compare(
s0.createdWords.size(), s1.createdWords.size());
}
});
System.out.println(bestSolution);
}
}
static class Solution
{
List<Character> letters;
List<String> createdWords;
public Solution(List<String> words, List<Character> letters)
{
this.letters = letters;
this.createdWords = computeCreatedWords(words, letters);
}
@Override
public String toString()
{
return letters.size() + " letters: " + letters
+ ", created words: " + createdWords;
}
}
private static List<String> computeCreatedWords(
List<String> words, List<Character> letters)
{
List<String> createdWords = new ArrayList<String>();
for (String word : words)
{
if (creates(letters, word))
{
createdWords.add(word);
}
}
return createdWords;
}
private static boolean creates(List<Character> letters, String word)
{
List<Character> copy = new ArrayList<Character>(letters);
for (int i=0; i<word.length(); i++)
{
Character c = Character.valueOf(word.charAt(i));
if (!copy.remove(c))
{
return false;
}
}
return true;
}
private static List<Character> lettersOf(String word)
{
List<Character> letters = new ArrayList<Character>();
for (int i=0; i<word.length(); i++)
{
letters.add(Character.valueOf(word.charAt(i)));
}
return letters;
}
private static Set<Character> allLettersOf(Iterable<String> words)
{
Set<Character> letters = new TreeSet<Character>();
for (String word : words)
{
letters.addAll(lettersOf(word));
}
return letters;
}
}
//=============================================================================
// These classes are taken from https://github.com/javagl/Combinatorics
/**
* A class providing an iterator over all combinations of a certain number
* of elements of a given set. For a set S with n = |S|, there are are n^k
* combinations of k elements of the set. This is the number of possible
* samples when doing sampling with replacement. Example:<br />
* <pre>
* S = { A,B,C }, n = |S| = 3
* k = 2
* m = n^k = 9
*
* Combinations:
* [A, A]
* [A, B]
* [A, C]
* [B, A]
* [B, B]
* [B, C]
* [C, A]
* [C, B]
* [C, C]
* </pre>
*
* @param <T> The type of the elements
*/
final class CombinationIterable<T> implements Iterable<List<T>>
{
/**
* The input elements
*/
private final List<T> input;
/**
* The sample size
*/
private final int sampleSize;
/**
* The total number of elements that the iterator will provide
*/
private final int numElements;
/**
* Creates an iterable over all multisets of
* 'sampleSize' elements of the given array.
*
* @param sampleSize The sample size
* @param input The input elements
*/
public CombinationIterable(int sampleSize, List<T> input)
{
this.sampleSize = sampleSize;
this.input = input;
numElements = (int) Math.pow(input.size(), sampleSize);
}
@Override
public Iterator<List<T>> iterator()
{
return new Iterator<List<T>>()
{
/**
* The element counter
*/
private int current = 0;
/**
* The indices of the elements that are currently chosen
*/
private final int chosen[] = new int[sampleSize];
@Override
public boolean hasNext()
{
return current < numElements;
}
@Override
public List<T> next()
{
if (!hasNext())
{
throw new NoSuchElementException("No more elements");
}
List<T> result = new ArrayList<T>(sampleSize);
for (int i = 0; i < sampleSize; i++)
{
result.add(input.get(chosen[i]));
}
increase();
current++;
return result;
}
/**
* Increases the k-ary representation of the selection of
* elements by one.
*/
private void increase()
{
// The array of 'chosen' elements for a set of size n
// effectively is a number represented in k-ary form,
// and thus, this method does nothing else than count.
// For example, when choosing 2 elements of a set with
// n=10, the contents of 'chosen' would represent all
// values
// 00, 01, 02,... 09,
// 10, 11, 12,... 19,
// ...
// 90, 91, 92, ...99
// with each digit indicating the index of the element
// of the input array that should be placed at the
// respective position of the output array.
int index = chosen.length - 1;
while (index >= 0)
{
if (chosen[index] < input.size() - 1)
{
chosen[index]++;
return;
}
chosen[index] = 0;
index--;
}
}
@Override
public void remove()
{
throw new UnsupportedOperationException(
"May not remove elements from a combination");
}
};
}
}
/**
* Utility methods used in the combinatorics package
*/
class Utils
{
/**
* Utility method for computing the factorial n! of a number n.
* The factorial of a number n is n*(n-1)*(n-2)*...*1, or more
* formally:<br />
* 0! = 1 <br />
* 1! = 1 <br />
* n! = n*(n-1)!<br />
*
* @param n The number of which the factorial should be computed
* @return The factorial, i.e. n!
*/
public static BigInteger factorial(int n)
{
BigInteger f = BigInteger.ONE;
for (int i = 2; i <= n; i++)
{
f = f.multiply(BigInteger.valueOf(i));
}
return f;
}
/**
* A magic utility method that happens to return the number of
* bits that are set to '1' in the given number.
*
* @param n The number whose bits should be counted
* @return The number of bits that are '1' in n
*/
public static int countBits(int n)
{
int m = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
return ((m + (m >> 3)) & 030707070707) % 63;
}
/**
* Add all elements from the given iterable into the given collection
*
* @param <T> A type that is related to the elements
* @param iterable The iterable
* @param collection The collection
*/
public static <T> void addAll(
Iterable<? extends T> iterable, Collection<? super T> collection)
{
for (T t : iterable)
{
collection.add(t);
}
}
/**
* Returns all elements from the given iterable as a list
*
* @param <T> A type that is related to the elements
* @param iterable The iterable
* @return The list
*/
public static <T> List<T> asList(Iterable<? extends T> iterable)
{
List<T> list = new ArrayList<T>();
addAll(iterable, list);
return list;
}
/**
* Returns all elements from the given iterable as a set
*
* @param <T> A type that is related to the elements
* @param iterable The iterable
* @return The set
*/
public static <T> Set<T> asSet(Iterable<? extends T> iterable)
{
Set<T> set = new LinkedHashSet<T>();
addAll(iterable, set);
return set;
}
/**
* Private constructor to prevent instantiation
*/
private Utils()
{
}
}
（请注意，与初始版本相比，代码中没有太多变化 - 基本上，它现在使用CombinationIterable来代替ChoiceIterable 。但是组合的数量远大于选择的数量，所以这个仅对于比初始解决方案小得多的输入才可行）。