{ "apple", "banana", "cherry" }
{ "apple", "cherry", "banana" }
{ "banana", "apple", "cherry" }
{ "banana", "cherry", "apple" }
{ "cherry", "apple", "banana" }
{ "cherry", "banana", "apple" }
4! = 4 * 3 * 2 * 1 = 24
{ "apple" }, { "banana" }, {"cherry" }
{ "apple", "banana" }
{ "apple", "cherry" }
{ "banana", "cherry" }
{ "apple", "banana", "cherry" }
public StringPerm(string[] atoms)
{
if (atoms == null) throw new ArgumentNullException("atoms");
if (!IsValid(atoms)) throw new ArgumentException("atoms");
this.element = new string[atoms.Length];
atoms.CopyTo(this.element, 0);
this.order = atoms.Length;
}
string[] atoms = new string[] { "ant", "bat", "cow", "dog" };
StringPerm p = new StringPerm(atoms);
public static bool IsValid(string[] e)
{
if (e == null) return false;
if (e.Length < 2) return false;
for (int i = 0; i < e.Length - 1; ++i)
{
if (e[i].CompareTo(e[i + 1]) >= 0) return false;
}
return true;
}
{ "ant", "bat",
"bat", "cow" }
public override string ToString()
{
StringBuilder result = new StringBuilder();
result.Append("{ ");
for (int i = 0; i < this.order; ++i)
{
result.Append(this.element[i]);
result.Append(" ");
}
result.Append("}");
return result;
}
{ "1" "3" "5" "4" "2" "0" }
{ "1" "4" "0" "2" "3" "5" }
{ "1" "4" "5" "3" "2" "0" }
{ "1" "4" "0" "2" "3" "5" }
{ "ant", "bat", "cow", "dog" }
{ "dog", "cow", "bat", "ant" }
string[] atoms = new string[] { "ant", "bat", "cow", "dog" };
Console.WriteLine("In lexicographical order, all permutations are:\n");
for(StringPerm p = new StringPerm(atoms); p != null; p = p.Successor())
{
Console.WriteLine(p.ToString());
}
{ "cow" "ant" "dog" "bat" }
(6! * 1) + (5! * 1) + (4! * 0) + (3! * 3) + (2! * 0) + (1! * 1) + (0! * 0) = 720 + 120 + 0 + 18 + 0 + 1 = 859
{ "cow", "ant", "dog", "bat" }
string[] atoms = new string[] { "ant", "bat", "cow", "dog" };
Console.WriteLine("\nJust element [13] computed directly is:");
p = new StringPerm(atoms, 13);
Console.WriteLine(" " + p.ToString());
string[] atoms = new string[] { "ant", "bat", "cow", "cow" };
StringPerm p = null;
Console.WriteLine("All permutations are:\n");
for (int k = 0; (ulong)k < StringPerm.FactorialLookup(4); ++k)
{
p = new StringPerm(atoms, k);
Console.WriteLine(k + " " + p.ToString());
}
public static ulong FactorialRecursive(int n)
{
if (n < 0) throw new ArgumentOutOfRangeException("n");
if (n == 0 || n == 1) return 1;
else return (ulong)n * FactorialRecursive(n - 1);
}
126,886,932,100,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000,000,000,000
20 * 19 * 18 *. .. * 2 * 1 = 2,432,902,008,176,640,000
ulong result = FactorialRecursive(21)in a program? You'd expect to throw an arithmetic overflow of some sort, but that is not what happens by default. The compiler will reach ulong.MaxValue (which is 18,446,744,073,709,551,615) and then wrap around, back to 0, and continue computing without any warnings. Note that the common language runtime (CLR) is capable of overflow and underflow checking on numeric operations, a feature you can enable at compile time. On top of this problem, there's really no compelling reason to use a recursive solution here. A second try at a factorial method is to compute the answer iteratively, something like this:
public static ulong FactorialCompute(int n)
{
if (n < 0 || n > 20)
throw new Exception("Input argument must be between 0 and 20");
ulong answer = 1;
for (int i = 1; i <= n; ++i) answer = checked(answer * (ulong)i);
return answer;
}
public static ulong FactorialLookup(int n)
{
if (n < 0 || n > 20)
throw new Exception("Input argument must be between 0 and 20");
ulong[] answers = new ulong[] { 1, 1, 2, 6, 24, 120, 720, 5040, 40320,
362880, 3628800, 39916800, 479001600, 6227020800, 87178291200,
1307674368000, 20922789888000, 355687428096000, 6402373705728000,
121645100408832000, 2432902008176640000 };
return answers[n];
}
Send your questions and comments for James to testrun@microsoft.com.