Ускорение работы программы - C# (177190)
Формулировка задачи:
доброго времени суток. Возникла следующая проблема:
Это код генерации перестановок с небольшими дополнениями. Мне необходимо запускать программу на данных для множества, состоящего из 16 элементов. А это 16! (16 факториал) перестановок. Программа в нынешнем виде будет работаь примерно 20 дней, что неприемлемо. Помогите, пожалуйста, советом, а лучше кодом: как можно усовершенствовать, что добавить/исправить. Заранее спасибо.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace GeneratePerms_Non_parallel_
{
class Program
{
public static List<int[]> listOfDiffVectors = new List<int[]>();
private static void Swap(ref int a, ref int b)
{
if (a == b) return;
a ^= b;
b ^= a;
a ^= b;
}
public static void GetPer(int[] list)
{
int x = list.Length - 1;
GetPer(list, 0, x);
}
private static void GetPer(int[] list, int k, int m)
{
if (k == m)
{
int[] diff = new int[list.Length];
int i = 0;
for (i = 0; i < list.Length; i++)
{
int d = 0;
if (i == list.Length - 1)
{
d = list[0] - list[i];
if (d < 0)
d += list.Length;
else
d %= list.Length;
diff[0] = d;
}
else
{
d = list[i + 1] - list[i];
if (d < 0)
d += list.Length;
else
d %= list.Length;
diff[i + 1] = d;
}
}
bool flag = false;
foreach (int[] temp in listOfDiffVectors)
if (temp.SequenceEqual(diff))
{
flag = true;
break;
}
if (!flag)
listOfDiffVectors.Add(diff);
}
else
for (int i = k; i <= m; i++)
{
Swap(ref list[k], ref list[i]);
GetPer(list, k + 1, m);
Swap(ref list[k], ref list[i]);
}
}
static void Main(string[] args)
{
//System.Diagnostics.Stopwatch sw = new Stopwatch();
int[] perm = new int[] { 0,1,2 };
//sw.Start();
GetPer(perm);
// sw.Stop();
//Console.WriteLine((sw.ElapsedMilliseconds / 1000.0).ToString());
Console.WriteLine("Press any key...");
Console.ReadKey();
}
}
}Решение задачи: «Ускорение работы программы»
textual
Листинг программы
foreach (int[] temp in listOfDiffVectors)
if (temp.SequenceEqual(diff))
{
flag = true;
break;
}
if (!flag)
listOfDiffVectors.Add(diff);