算法:里程表/冲击力
本文关键字:冲击力 里程表 算法 | 更新日期: 2023-09-27 17:48:49
我想用C#风格的语言编写一个类似里程表的方法,但不只是使用0-9表示字符,而是使用任何一组字符。它或多或少会像一个暴力应用程序。
如果我传入一个从0到J的字符数组,并将长度设置为5,我希望得到类似00000、00001、00002…HJJJJ、IJJJJJ、JJJJJ的结果。
这是基地,请帮我扩展:
protected void Main()
{
char[] chars = new char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J' };
BruteForce(chars, 5);
}
private void BruteForce(char[] chars, int length)
{
// for-loop (?) console-writing all possible combinations from 00000 to JJJJJ
// (when passed in length is 5)
// TODO: Implement code...
}
这不是完全"递归而非多循环"的重复,但它非常接近。如果这对你没有帮助,我会写一个解决方案。
编辑:这是一个非递归的解决方案。递归的返回IEnumerable<string>
稍微有点困难,但返回迭代器提供了一个很好的接口IMO:)
private static IEnumerable<string> GetAllMatches(char[] chars, int length)
{
int[] indexes = new int[length];
char[] current = new char[length];
for (int i=0; i < length; i++)
{
current[i] = chars[0];
}
do
{
yield return new string(current);
}
while (Increment(indexes, current, chars));
}
private static bool Increment(int[] indexes, char[] current, char[] chars)
{
int position = indexes.Length-1;
while (position >= 0)
{
indexes[position]++;
if (indexes[position] < chars.Length)
{
current[position] = chars[indexes[position]];
return true;
}
indexes[position] = 0;
current[position] = chars[0];
position--;
}
return false;
}
这是我找到的解决方案之一。我喜欢它的紧凑性和分离性:
private static char[] characters =
new char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J' };
// length: The length of the string created by bruteforce
public static void PerformBruteForce(int length) {
int charactersLength = characters.Length;
int[] odometer = new int[length];
long size = (long)Math.Pow(charactersLength, length);
for (int i = 0; i < size; i++) {
WriteBruteForce(odometer, characters);
int position = 0;
do {
odometer[position] += 1;
odometer[position] %= charactersLength;
} while (odometer[position++] == 0 && position < length);
}
}
private static void WriteBruteForce(int[] odometer, char[] characters) {
// Print backwards
for (int i = odometer.Length - 1; i >= 0; i--) {
Console.Write(characters[odometer[i]]);
}
Console.WriteLine();
}
搜索排列。
然而,如果你只是在处理"十六进制"范围,只需执行以下操作:
for (int i = 0; i < (1 << 24); i++)
string s = i.ToString("X6");
下面是我以前为此使用过的一个类。。。顾名思义,它根据所提供的字符集中的字符数以不同的基数进行计数。希望它有用。。。
public class BaseNCounter
{
public char[] CharSet { get; set; }
public int Power { get; set; }
public BaseNCounter() { }
public IEnumerable<string> Count() {
long max = (long)Math.Pow((double)this.CharSet.Length, (double)this.Power);
long[] counts = new long[this.Power];
for(long i = 0; i < max; i++)
yield return IncrementArray(ref counts, i);
}
public string IncrementArray(ref long[] counts, long count) {
long temp = count;
for (int i = this.Power - 1; i >= 0 ; i--) {
long pow = (long)Math.Pow(this.CharSet.Length, i);
counts[i] = temp / pow;
temp = temp % pow;
}
StringBuilder sb = new StringBuilder();
foreach (int c in counts) sb.Insert(0, this.CharSet[c]);
return sb.ToString();
}
}
以下是控制台应用程序中的几个使用场景。
class Program
{
static void Main(string[] args)
{
BaseNCounter c = new BaseNCounter() {
CharSet = new char [] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' },
Power = 2};
foreach(string cc in c.Count())
Console.Write("{0} ,", cc);
Console.WriteLine("");
BaseNCounter c2 = new BaseNCounter()
{
CharSet = new char[] { 'x', 'q', 'r', '9'},
Power = 3
};
foreach (string cc in c2.Count())
Console.Write("{0} ,", cc);
Console.Read();
}
}