Nie chce mi się odpowiadać w kontekście pojedynczych wpisów. Ten problem potraktowałem jako swoiste wyzwanie optymalizacyjne.
W pierwszej kolejności sprawdziłem jak się miewa backtracking przedstawiony wyżej.
Wypadł dosyć tak sobie, wysypuje się już przy 7 wyrazach.
Zaciekawił mnie też pomysł z wykorzystaniem kilku rdzeni - nie wiadomo może dla autora pomysł przypadłby do gustu, bo 2x to już standard itd. itd. (dodatkowo jest coś jak HT - testowany osobiście, daje troche kopa :) )
Wiadomo, że algorytm iteracyjny będzie znacznie szybszy i wydajniejszy pod każdym względem, ale autor zaznaczył, że wyrazów będzie maksymalnie 5 (dobrze zrozumiałem?) takze można to zaniedbać :P
Jako, że w C# nie mam dużego stażu więc wymodziłem klasę spełniającą wymagane czynności:
generuje ona listę takich permutacji z wykorzystaniem maksymalnie 5 rdzeni (gdyż tyle maksymalnie jest wyrazów według autora)
Zrobiłem testy (niestety dla 6 słów, gdyż algorytm autora tematu się wysypuje przy większej ilości) i otrzymałem następujące wyniki:
Lista ma 720 zdan //algorytm autora
Wygenerowanie listy zajelo: 41 ms
Nacisnij ENTER by rozpoczac drugi test porownawczy
Lista ma 720 zdan //z podzialem na watki (+ inne podejscie do sprawy)
Wygenerowanie listy zajelo: 15 ms
Nacisnij ENTER by zakonczyc ocenianie
Zamieszczam cały kod programu i mam nadzieję, że przyda się jakoś autorowi :)
Oczywiście zachęcam do skorzystania z iteracyjnego pomysłu jeżeli zależy Ci na jeszcze większej wydajności
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
namespace ConsoleApplication1
{
class Program
{
private void StworzWariacje(string wyrazenie)
{
string[] podzielone = wyrazenie.Split(' ');
for (int i = 0; i < podzielone.Length - 1; i++)
{
StringBuilder noweWyrazenie = new StringBuilder(string.Empty);
for (int j = 0; j < i; j++)
{
noweWyrazenie.Append(podzielone[j]);
noweWyrazenie.Append(' ');
}
noweWyrazenie.Append(podzielone[i + 1]);
noweWyrazenie.Append(' ');
noweWyrazenie.Append(podzielone[i]);
noweWyrazenie.Append(' ');
for (int j = i + 2; j < podzielone.Length; j++)
{
noweWyrazenie.Append(podzielone[j]);
noweWyrazenie.Append(' ');
}
wyrazenie = noweWyrazenie.ToString();
wyrazenie = wyrazenie.Remove(wyrazenie.Length - 1);
if (!(lista.Contains(wyrazenie)))
{
lista.Add(wyrazenie);
StworzWariacje(wyrazenie);
}
}
}
public List<String> lista = new List<string>();
static void Main(string[] args)
{
DateTime start = DateTime.Now;
Program main = new Program();
main.StworzWariacje("wyraz1 wyraz2 wyraz3 wyraz4 wyraz5 wyraz6");
System.Console.WriteLine("Lista ma {0} zdan",main.lista.Count);
DateTime stop = DateTime.Now;
System.Console.WriteLine("Wygenerowanie listy zajelo: {0:0} ms", stop.TimeOfDay.TotalMilliseconds-start.TimeOfDay.TotalMilliseconds);
System.Console.WriteLine("Nacisnij ENTER by rozpoczac drugi test porownawczy");
System.Console.ReadKey();
start = DateTime.Now;
BackTrackMTH test = new BackTrackMTH("wyraz1 wyraz2 wyraz3 wyraz4 wyraz5 wyraz6");
System.Console.WriteLine("Lista ma {0} zdan",test.generateList().Count);
stop = DateTime.Now;
System.Console.WriteLine("Wygenerowanie listy zajelo: {0:0} ms", stop.TimeOfDay.TotalMilliseconds - start.TimeOfDay.TotalMilliseconds);
System.Console.WriteLine("Nacisnij ENTER by zakonczyc ocenianie");
System.Console.ReadKey();
}
}
//-----------------
class BackTrackMTH
{
String[] tab;
Thread[] pool;
Semaphore sem = new Semaphore(1, 1);
List<String> str;
private void generate(Object nr)
{
int i = (int)nr;
bool[] uzyte=new bool[tab.Length];
for (int k = 0; k < tab.Length; k++)
uzyte[k] = false;
uzyte[i] = true;
backtracking(1, new StringBuilder(tab[i]), uzyte);
}
private void backtracking(int slowo, StringBuilder strb, bool[] uzyte)
{
if (slowo == tab.Length)
{
sem.WaitOne();
str.Add(strb.ToString());
sem.Release();
return;
}
for (int i = 0; i < tab.Length; i++)
{
if (uzyte[i] == false)
{
uzyte[i] = true;
strb.Append(' ');
strb.Append(tab[i]);
backtracking(slowo + 1, strb, uzyte);
strb.Remove(strb.Length - tab[i].Length - 1, tab[i].Length + 1);
uzyte[i] = false;
}
}
}
public BackTrackMTH(String wyrazenie)
{
tab = wyrazenie.Split(' ');
pool = new Thread[tab.Length];
ParameterizedThreadStart th = new ParameterizedThreadStart(generate);
for (int i = 0; i < tab.Length; i++)
{
pool[i] = new Thread(th);
}
str=new List<string>();
}
public List<String> generateList()
{
for (int i=0;i<tab.Length;i++)
pool[i].Start(i);
for (int i = 0; i < tab.Length; i++)
pool[i].Join();
return this.str;
}
}
}
No i oczywiście przyznam się, że nie wpadłbym na pomysł z iteracją zaproponowaną przez @quetzalcoatl, gdyż ostatnio większość problemów z którymi się stykam to backtracking więc już tylko o tym myślę :)
Także potraktuj już ten kod jako taką sobie ciekawostkę i implementuj najlepsze dostępne rozwiązanie :)
