Dies könnte leichter mit einem Beispielcode erklärt werden, ich habe die folgenden zwei Funktionen. Die erste schafft alle Sätze von Saiten einer bestimmten Länge (size) und Zeichen (group)Wie man eine Menge Sätze in c optimal und schnell komprimiert #
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);
}
Die zweite Funktion eine Reihe von Sätzen komprimiert basierend auf allen möglichen Begegnungen:
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);
}
Zum Beispiel:
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]);
}
Will Ausgang:
ABCD
ABCE
ABCF
ADEF
BDEF
CDEF
Dies ist ein minimaler Satz von Strings mit 4 Zeichen Länge, die jede 3-Buchstaben-Kombination der Buchstaben A-F enthalten, unabhängig von der Reihenfolge, in der sie auftreten. Dies funktioniert gut und scheint mit einem wichtigen Vorbehalt richtig zu skalieren: Es dauert exponentiell länger bei jeder Erhöhung der anfänglichen Satzgröße, der Zielsatzgröße und der erforderlichen Anzahl übereinstimmender Zeichen in den resultierenden Mengen. Gibt es eine Möglichkeit, dies schneller oder einen optimaleren Algorithmus zu erreichen, um diese Aufgabe zu erfüllen?