1
これはコードのサンプルで簡単に説明できますが、次の2つの機能があります。例えばCのセットを最適かつ迅速に圧縮する方法＃
private List<string> compressSets(List<string> sets, List<string> possible)
{
List<string> working = null;
List<string> ret = new List<string>();
List<int> indices = new List<int>() { 0 };
List<int> indicesLow = null;
while (indices.Count < possible.Count)
{
working = new List<string>(sets);
for (int i = 0; i < indices.Count; i++)
{
for (int w = working.Count - 1; w >= 0; w--)
{
if (this.ContainsAll(possible[indices[i]], working[w])) working.RemoveAt(w);
}
}
if (working.Count < 1)
{
if ((indicesLow == null) || (indicesLow.Count > indices.Count))
{
for (int i = 0; i < indices.Count; i++)
{
ret.Add(possible[indices[i]]);
}
return (ret);
}
}
for (int i = indices.Count - 1; i >= 0; i--)
{
if (indices[i] < (possible.Count - (indices.Count - i)))
{
indices[i]++;
for (int j = i + 1; j < indices.Count; j++)
{
indices[j] = indices[j - 1] + 1;
}
break;
}
}
if (indices[0] >= (possible.Count - indices.Count))
{
for (int i = 0; i < indices.Count; i++) indices[i] = i;
indices.Add(indices.Count);
}
}
return (ret);
}
public bool ContainsAll(string set, string subset)
{
/*foreach (T item in subset)
{
if (!set.Contains(item)) return (false);
}
return (true);*/
for (var i = 0; i < subset.Length; i++)
{
if (set.IndexOf(subset[i]) < 0) return (false);
}
return (true);
}
：第一は、第二の機能は、すべての可能な一致に基づいて、集合の集合を圧縮
private List<string> generateSets(int size, IList<string> group)
{
List<string> ret = new List<string>();
int[] indices = new int[size];
for (int i = 0; i < size; i++) indices[i] = i;
ret.Add((size > 0 ? group[indices[0]] : "") +
(size > 1 ? group[indices[1]] : "") +
(size > 2 ? group[indices[2]] : "") +
(size > 3 ? group[indices[3]] : "") +
(size > 4 ? group[indices[4]] : ""));
while (indices[0] < (group.Count - size))
{
for (int i = size - 1; i >= 0; i--)
{
if (indices[i] < (group.Count - (indices.Length - i)))
{
indices[i]++;
for (int j = i + 1; j < size; j++)
{
indices[j] = indices[j - 1] + 1;
}
break;
}
}
ret.Add((size > 0 ? group[indices[0]] : "") +
(size > 1 ? group[indices[1]] : "") +
(size > 2 ? group[indices[2]] : "") +
(size > 3 ? group[indices[3]] : "") +
(size > 4 ? group[indices[4]] : ""));
}
return (ret);
}
所定の長さの文字列（size）及び文字（group）のすべてのセットを作成します。
List<string> group = new List<string>();
group.Add("A");
group.Add("B");
group.Add("C");
group.Add("D");
group.Add("E");
group.Add("F");
List<string> sets3 = this.generateSets(3, group);
List<string> sets4 = this.generateSets(4, group);
List<string> sets = this.compressSets(sets3, sets4);
for (int i = 0; i < sets.Count; i++)
{
Debug.WriteLine(sets[i]);
}
ウィル出力：
ABCD
ABCE
ABCF
ADEF
BDEF
CDEF
3文字の長さの文字A~Fの組み合わせを含む4文字の文字列の最小セットです。文字の順序は関係ありません。これはうまく動作し、1つの大きな注意点で正しくスケールアップされているように見えます。初期セットサイズ、ターゲットセットサイズ、および結果セット内の一致する文字の必要な数が増加するたびに指数関数的に長くなります。このタスクを達成するために、これを高速化したり、より最適なアルゴリズムにする方法はありますか？