Speed up N(P) problem search - Sum-Square Problem
up vote
0
down vote
favorite
Speed up N(P) problem search - Sum-Square Problem
I was wondering if anyone could help me figuring out ways to speed up a small programm I was working on.
The problem is a math exercise called the Sum-Square Problem (https://youtu.be/G1m7goLCJDY).
So you take a list of continuous integers starting at 1 to N and see if you can reorder them so that the sum of each pair makes a square.
So for example:
1-3-6-10-15-
or
1-15-10-6-3-13-12-4-5-11-14-2-7-9-
The trick is to use all the numbers in the domain [1,N]. Obviously you can either find just one solution proving that there is a solution for [1,N] or you can show all the solutions for that domain. In the latter case you will get a reverse solution for each solution obviously, plus you can get so-called cyclic solutions where the start and end also make a square.
Now increasing N (after 23 there seems to be a solution for each N - not proven) exponentially increases the number of possible branches or paths you can try.
My program first was simple loops which checked basically every option. This meant my computer (simple i9 core) started to struggle (processing > 1h) at around N=30. I then changed method and first created a table or matrix containing only those numbers that would create a square for each number [1,N]. So for N=15 (first possible N with a solution) you would get:
For N=15 the squares possible are: 4, 9, 16, 25
1 - 3, 8, 15
2 - 7, 14
3 - 1, 6, 13
....
15 - 1, 10
I then traversed through this table to find possible solutions. If a path dead-ended the program backtracks until there is anpther branch, tries that one, backtracks, etc.
This took me up to about N=50 before it started taking too long (>1h) for my taste.
Up til then I was working with Lists (using C#) so I tried HashSets, that took it up to about N = 70. Now I seem to be stuck.
I either:
1) have to find another function that can process running through lists and paths faster, or
2) think of a completely different approach in mathematically solving this
3) step up the processing power
Does anyone have a smarter suggestion then the ones I thought of myself?
My code (C#):
using System;
using System.Collections.Generic;
namespace SumSquare
{
public class CalculateHash
{
List<List<int>> matrix = new List<List<int>>();
List<int> squares = new List<int>();
List<int> branch = new List<int>();
HashSet<int> defaultList = new HashSet<int>();
HashSet<int> worklist = new HashSet<int>();
int currentN, currentSet, currentIndex; //, prevIndex;
int max;
List<int> prevIndexSet = new List<int>(); //Holds prevSet index
bool going, going2;
DateTime startTime;
int successes = 0;
int cyclic = 0;
TimeSpan elapsed;
public void Calculate(int maxNum)
{
max = maxNum;
squares = FillSquares(max);
matrix = CreateMatrix(squares, max);
startTime = DateTime.Now;
for (int i = 1; i <= max; i++)
{
branch.Clear();
worklist.Clear();
branch.Add(i);
worklist = FillDefaultList(max);//Fill with all but current start number
worklist.Remove(i);
currentIndex = 0;
currentN = matrix[i][0]; //Get first element
currentSet = i; //remember current set, starting number
going = true;
while (going)
{
if (worklist.Contains(currentN))//Is this number still available?
{
branch.Add(currentN); //add currentN
worklist.Remove(currentN);//Clean up worklist
if (worklist.Count == 0) //All numbers processed! HIT
{
successes++;
ShowSucces();
//to quit at the first success
//going = false; //Quit at first success
//i = max + 1; //quit programm
}
prevIndexSet.Add(currentIndex);
currentSet = currentN;
currentN = matrix[currentSet][0];
currentIndex = 0;//reset for next Set
}
else //number already in use!
{
currentIndex++;
going2 = true;
if (currentIndex == matrix[currentSet].Count) //Used up all the numbers in this set?
{
while (going2)
{
int prevSet = branch[branch.Count - 1];//get the last number added at which this branch halted
branch.RemoveAt(branch.Count - 1); //remove this last number
//We need to add the number prevSet back into the workList BUT
//it needs to go at the correct location!! To keep the numbers in order
worklist.Add(prevSet); //Add the number back
if (branch.Count == 0) //We've exhausted all the possible paths starting with number (i)
{
going2 = false; //break out if this while
going = false; //break out of parent while
}
else
{
currentSet = branch[branch.Count - 1]; //Get the last number of the previous set
currentIndex = prevIndexSet[prevIndexSet.Count - 1] + 1; //Get the position in that set whee we last stopped and get the next position
prevIndexSet.RemoveAt(prevIndexSet.Count - 1);//remove that index reference
if (currentIndex < matrix[currentSet].Count) //No more numbers in this set
{
currentN = matrix[currentSet][currentIndex]; //carry on
going2 = false;
}
}
}
}
else
{
currentN = matrix[currentSet][currentIndex]; //Get the next number in this Set
}
}
}
}
TimeSpan elapsedTime = DateTime.Now - startTime;
Console.WriteLine("Time elapsed: " + elapsedTime.TotalSeconds);
Console.WriteLine("Number of successes: " + (successes * 0.5));
Console.WriteLine("Number of cyclic successes: " + cyclic);
Console.ReadKey();
}
List<List<int>> CreateMatrix(List<int> s, int m)
{
//This creates a 2-dimensional List, First dimension is [1,max], Second dimension the number need to get a sum when added to the current number
List<List<int>> t = new List<List<int>>();
t.Add(new List<int>()); //Element 0 is empty
for (int i = 1; i <= max; i++)
{
List<int> tt = new List<int>();
for (int j = 0; j < s.Count; j++)
{
int difference = s[j] - i;
if ((difference > 0) && (difference <= max) && difference != i) //Needs to be >0 and <=max
{
tt.Add(s[j] - i); //Now add the result: Square - currentINT
}
}
t.Add(tt); //Now stuff it into the parent List where INT=1 is Index=0
}
return t;
}
HashSet<int> FillDefaultList(int maxInt) //Fills a List with [1,max] integers
{
HashSet<int> l = new HashSet<int>();
for (int i = 1; i <= max; i++)
{
l.Add(i);
}
return l;
}
List<int> FillSquares(int max) //Creates a list of the squares of all values from [2,max] below the max + max-1 sum
{
List<int> l = new List<int>();
int maxSum = max + (max - 1);
for (int i = 2; i < max; i++)
{
if ((i * i) <= maxSum)
{
l.Add(i * i);
}
}
return l;
}
List<int> RemoveElement(List<int> list, int number)
{
List<int> l = new List<int>();
for (int i = 0; i < list.Count; i++)
{
if (list[i] != number)
{
l.Add(list[i]);
}
}
return l;
}
HashSet<int> FillWorklist(HashSet<int> defList, int cNum)
{
HashSet<int> l = defList;
l.Remove(cNum);
return l;
}
void ShowSucces()
{
Console.Write("Found a path with starting number: " + branch[0]);
if (squares.Contains(branch[0] + branch[branch.Count - 1])) //Is it cyclic?
{
cyclic++;
Console.WriteLine(" - This branch is cyclic! ");
}
else
{
Console.WriteLine();
}
for (int i = 0; i < max - 1; i++)
{
Console.Write(branch[i] + ",");
}
Console.WriteLine(branch[max - 1]);
}
}
}
c# math iteration np
asked Nov 19 at 11:42
Dutchottie
1
add a comment |
up vote
0
down vote
favorite
Speed up N(P) problem search - Sum-Square Problem
I was wondering if anyone could help me figuring out ways to speed up a small programm I was working on.
The problem is a math exercise called the Sum-Square Problem (https://youtu.be/G1m7goLCJDY).
So you take a list of continuous integers starting at 1 to N and see if you can reorder them so that the sum of each pair makes a square.
So for example:
1-3-6-10-15-
or
1-15-10-6-3-13-12-4-5-11-14-2-7-9-
The trick is to use all the numbers in the domain [1,N]. Obviously you can either find just one solution proving that there is a solution for [1,N] or you can show all the solutions for that domain. In the latter case you will get a reverse solution for each solution obviously, plus you can get so-called cyclic solutions where the start and end also make a square.
Now increasing N (after 23 there seems to be a solution for each N - not proven) exponentially increases the number of possible branches or paths you can try.
My program first was simple loops which checked basically every option. This meant my computer (simple i9 core) started to struggle (processing > 1h) at around N=30. I then changed method and first created a table or matrix containing only those numbers that would create a square for each number [1,N]. So for N=15 (first possible N with a solution) you would get:
For N=15 the squares possible are: 4, 9, 16, 25
1 - 3, 8, 15
2 - 7, 14
3 - 1, 6, 13
....
15 - 1, 10
I then traversed through this table to find possible solutions. If a path dead-ended the program backtracks until there is anpther branch, tries that one, backtracks, etc.
This took me up to about N=50 before it started taking too long (>1h) for my taste.
Up til then I was working with Lists (using C#) so I tried HashSets, that took it up to about N = 70. Now I seem to be stuck.
I either:
1) have to find another function that can process running through lists and paths faster, or
2) think of a completely different approach in mathematically solving this
3) step up the processing power
Does anyone have a smarter suggestion then the ones I thought of myself?
My code (C#):
using System;
using System.Collections.Generic;
namespace SumSquare
{
public class CalculateHash
{
List<List<int>> matrix = new List<List<int>>();
List<int> squares = new List<int>();
List<int> branch = new List<int>();
HashSet<int> defaultList = new HashSet<int>();
HashSet<int> worklist = new HashSet<int>();
int currentN, currentSet, currentIndex; //, prevIndex;
int max;
List<int> prevIndexSet = new List<int>(); //Holds prevSet index
bool going, going2;
DateTime startTime;
int successes = 0;
int cyclic = 0;
TimeSpan elapsed;
public void Calculate(int maxNum)
{
max = maxNum;
squares = FillSquares(max);
matrix = CreateMatrix(squares, max);
startTime = DateTime.Now;
for (int i = 1; i <= max; i++)
{
branch.Clear();
worklist.Clear();
branch.Add(i);
worklist = FillDefaultList(max);//Fill with all but current start number
worklist.Remove(i);
currentIndex = 0;
currentN = matrix[i][0]; //Get first element
currentSet = i; //remember current set, starting number
going = true;
while (going)
{
if (worklist.Contains(currentN))//Is this number still available?
{
branch.Add(currentN); //add currentN
worklist.Remove(currentN);//Clean up worklist
if (worklist.Count == 0) //All numbers processed! HIT
{
successes++;
ShowSucces();
//to quit at the first success
//going = false; //Quit at first success
//i = max + 1; //quit programm
}
prevIndexSet.Add(currentIndex);
currentSet = currentN;
currentN = matrix[currentSet][0];
currentIndex = 0;//reset for next Set
}
else //number already in use!
{
currentIndex++;
going2 = true;
if (currentIndex == matrix[currentSet].Count) //Used up all the numbers in this set?
{
while (going2)
{
int prevSet = branch[branch.Count - 1];//get the last number added at which this branch halted
branch.RemoveAt(branch.Count - 1); //remove this last number
//We need to add the number prevSet back into the workList BUT
//it needs to go at the correct location!! To keep the numbers in order
worklist.Add(prevSet); //Add the number back
if (branch.Count == 0) //We've exhausted all the possible paths starting with number (i)
{
going2 = false; //break out if this while
going = false; //break out of parent while
}
else
{
currentSet = branch[branch.Count - 1]; //Get the last number of the previous set
currentIndex = prevIndexSet[prevIndexSet.Count - 1] + 1; //Get the position in that set whee we last stopped and get the next position
prevIndexSet.RemoveAt(prevIndexSet.Count - 1);//remove that index reference
if (currentIndex < matrix[currentSet].Count) //No more numbers in this set
{
currentN = matrix[currentSet][currentIndex]; //carry on
going2 = false;
}
}
}
}
else
{
currentN = matrix[currentSet][currentIndex]; //Get the next number in this Set
}
}
}
}
TimeSpan elapsedTime = DateTime.Now - startTime;
Console.WriteLine("Time elapsed: " + elapsedTime.TotalSeconds);
Console.WriteLine("Number of successes: " + (successes * 0.5));
Console.WriteLine("Number of cyclic successes: " + cyclic);
Console.ReadKey();
}
List<List<int>> CreateMatrix(List<int> s, int m)
{
//This creates a 2-dimensional List, First dimension is [1,max], Second dimension the number need to get a sum when added to the current number
List<List<int>> t = new List<List<int>>();
t.Add(new List<int>()); //Element 0 is empty
for (int i = 1; i <= max; i++)
{
List<int> tt = new List<int>();
for (int j = 0; j < s.Count; j++)
{
int difference = s[j] - i;
if ((difference > 0) && (difference <= max) && difference != i) //Needs to be >0 and <=max
{
tt.Add(s[j] - i); //Now add the result: Square - currentINT
}
}
t.Add(tt); //Now stuff it into the parent List where INT=1 is Index=0
}
return t;
}
HashSet<int> FillDefaultList(int maxInt) //Fills a List with [1,max] integers
{
HashSet<int> l = new HashSet<int>();
for (int i = 1; i <= max; i++)
{
l.Add(i);
}
return l;
}
List<int> FillSquares(int max) //Creates a list of the squares of all values from [2,max] below the max + max-1 sum
{
List<int> l = new List<int>();
int maxSum = max + (max - 1);
for (int i = 2; i < max; i++)
{
if ((i * i) <= maxSum)
{
l.Add(i * i);
}
}
return l;
}
List<int> RemoveElement(List<int> list, int number)
{
List<int> l = new List<int>();
for (int i = 0; i < list.Count; i++)
{
if (list[i] != number)
{
l.Add(list[i]);
}
}
return l;
}
HashSet<int> FillWorklist(HashSet<int> defList, int cNum)
{
HashSet<int> l = defList;
l.Remove(cNum);
return l;
}
void ShowSucces()
{
Console.Write("Found a path with starting number: " + branch[0]);
if (squares.Contains(branch[0] + branch[branch.Count - 1])) //Is it cyclic?
{
cyclic++;
Console.WriteLine(" - This branch is cyclic! ");
}
else
{
Console.WriteLine();
}
for (int i = 0; i < max - 1; i++)
{
Console.Write(branch[i] + ",");
}
Console.WriteLine(branch[max - 1]);
}
}
}
c# math iteration np
asked Nov 19 at 11:42
Dutchottie
1
This may be better suited for cs.stackexchange.com
– Martin Wiboe
Nov 19 at 11:46
Let numbers (1,2,3...) be vertexes which are connected by edge if and only if the sum is a square (i.e.4and45are connected since4 + 45 == 49 == 7**2when3and8are not connected:3 + 8 == 11- not a square). So the initial task is a Hamiltonian Path Problem and you can try solving it with existing solvers. reference.wolfram.com/language/ref/FindHamiltonianPath.html
– Dmitry Bychenko
Nov 19 at 12:16
@Martin Wiboe: Thanks! I checked it and they primarily discuss if this is a true N(P) problem and not so much smart programming solutions.
– Dutchottie
Nov 20 at 12:16
@Dmitry Bychenko: Yes ofc you're correct. It is a special case of finding an Hamiltonian path. However as far as I know you can only solve this by brute force (and some smart avoiding using too much force). The question however remains: how to approach such a brute force with the least force - ie. the fastest processing?
– Dutchottie
Nov 20 at 12:16
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Speed up N(P) problem search - Sum-Square Problem
I was wondering if anyone could help me figuring out ways to speed up a small programm I was working on.
The problem is a math exercise called the Sum-Square Problem (https://youtu.be/G1m7goLCJDY).
So you take a list of continuous integers starting at 1 to N and see if you can reorder them so that the sum of each pair makes a square.
So for example:
1-3-6-10-15-
or
1-15-10-6-3-13-12-4-5-11-14-2-7-9-
The trick is to use all the numbers in the domain [1,N]. Obviously you can either find just one solution proving that there is a solution for [1,N] or you can show all the solutions for that domain. In the latter case you will get a reverse solution for each solution obviously, plus you can get so-called cyclic solutions where the start and end also make a square.
Now increasing N (after 23 there seems to be a solution for each N - not proven) exponentially increases the number of possible branches or paths you can try.
My program first was simple loops which checked basically every option. This meant my computer (simple i9 core) started to struggle (processing > 1h) at around N=30. I then changed method and first created a table or matrix containing only those numbers that would create a square for each number [1,N]. So for N=15 (first possible N with a solution) you would get:
For N=15 the squares possible are: 4, 9, 16, 25
1 - 3, 8, 15
2 - 7, 14
3 - 1, 6, 13
....
15 - 1, 10
I then traversed through this table to find possible solutions. If a path dead-ended the program backtracks until there is anpther branch, tries that one, backtracks, etc.
This took me up to about N=50 before it started taking too long (>1h) for my taste.
Up til then I was working with Lists (using C#) so I tried HashSets, that took it up to about N = 70. Now I seem to be stuck.
I either:
1) have to find another function that can process running through lists and paths faster, or
2) think of a completely different approach in mathematically solving this
3) step up the processing power
Does anyone have a smarter suggestion then the ones I thought of myself?
My code (C#):
using System;
using System.Collections.Generic;
namespace SumSquare
{
public class CalculateHash
{
List<List<int>> matrix = new List<List<int>>();
List<int> squares = new List<int>();
List<int> branch = new List<int>();
HashSet<int> defaultList = new HashSet<int>();
HashSet<int> worklist = new HashSet<int>();
int currentN, currentSet, currentIndex; //, prevIndex;
int max;
List<int> prevIndexSet = new List<int>(); //Holds prevSet index
bool going, going2;
DateTime startTime;
int successes = 0;
int cyclic = 0;
TimeSpan elapsed;
public void Calculate(int maxNum)
{
max = maxNum;
squares = FillSquares(max);
matrix = CreateMatrix(squares, max);
startTime = DateTime.Now;
for (int i = 1; i <= max; i++)
{
branch.Clear();
worklist.Clear();
branch.Add(i);
worklist = FillDefaultList(max);//Fill with all but current start number
worklist.Remove(i);
currentIndex = 0;
currentN = matrix[i][0]; //Get first element
currentSet = i; //remember current set, starting number
going = true;
while (going)
{
if (worklist.Contains(currentN))//Is this number still available?
{
branch.Add(currentN); //add currentN
worklist.Remove(currentN);//Clean up worklist
if (worklist.Count == 0) //All numbers processed! HIT
{
successes++;
ShowSucces();
//to quit at the first success
//going = false; //Quit at first success
//i = max + 1; //quit programm
}
prevIndexSet.Add(currentIndex);
currentSet = currentN;
currentN = matrix[currentSet][0];
currentIndex = 0;//reset for next Set
}
else //number already in use!
{
currentIndex++;
going2 = true;
if (currentIndex == matrix[currentSet].Count) //Used up all the numbers in this set?
{
while (going2)
{
int prevSet = branch[branch.Count - 1];//get the last number added at which this branch halted
branch.RemoveAt(branch.Count - 1); //remove this last number
//We need to add the number prevSet back into the workList BUT
//it needs to go at the correct location!! To keep the numbers in order
worklist.Add(prevSet); //Add the number back
if (branch.Count == 0) //We've exhausted all the possible paths starting with number (i)
{
going2 = false; //break out if this while
going = false; //break out of parent while
}
else
{
currentSet = branch[branch.Count - 1]; //Get the last number of the previous set
currentIndex = prevIndexSet[prevIndexSet.Count - 1] + 1; //Get the position in that set whee we last stopped and get the next position
prevIndexSet.RemoveAt(prevIndexSet.Count - 1);//remove that index reference
if (currentIndex < matrix[currentSet].Count) //No more numbers in this set
{
currentN = matrix[currentSet][currentIndex]; //carry on
going2 = false;
}
}
}
}
else
{
currentN = matrix[currentSet][currentIndex]; //Get the next number in this Set
}
}
}
}
TimeSpan elapsedTime = DateTime.Now - startTime;
Console.WriteLine("Time elapsed: " + elapsedTime.TotalSeconds);
Console.WriteLine("Number of successes: " + (successes * 0.5));
Console.WriteLine("Number of cyclic successes: " + cyclic);
Console.ReadKey();
}
List<List<int>> CreateMatrix(List<int> s, int m)
{
//This creates a 2-dimensional List, First dimension is [1,max], Second dimension the number need to get a sum when added to the current number
List<List<int>> t = new List<List<int>>();
t.Add(new List<int>()); //Element 0 is empty
for (int i = 1; i <= max; i++)
{
List<int> tt = new List<int>();
for (int j = 0; j < s.Count; j++)
{
int difference = s[j] - i;
if ((difference > 0) && (difference <= max) && difference != i) //Needs to be >0 and <=max
{
tt.Add(s[j] - i); //Now add the result: Square - currentINT
}
}
t.Add(tt); //Now stuff it into the parent List where INT=1 is Index=0
}
return t;
}
HashSet<int> FillDefaultList(int maxInt) //Fills a List with [1,max] integers
{
HashSet<int> l = new HashSet<int>();
for (int i = 1; i <= max; i++)
{
l.Add(i);
}
return l;
}
List<int> FillSquares(int max) //Creates a list of the squares of all values from [2,max] below the max + max-1 sum
{
List<int> l = new List<int>();
int maxSum = max + (max - 1);
for (int i = 2; i < max; i++)
{
if ((i * i) <= maxSum)
{
l.Add(i * i);
}
}
return l;
}
List<int> RemoveElement(List<int> list, int number)
{
List<int> l = new List<int>();
for (int i = 0; i < list.Count; i++)
{
if (list[i] != number)
{
l.Add(list[i]);
}
}
return l;
}
HashSet<int> FillWorklist(HashSet<int> defList, int cNum)
{
HashSet<int> l = defList;
l.Remove(cNum);
return l;
}
void ShowSucces()
{
Console.Write("Found a path with starting number: " + branch[0]);
if (squares.Contains(branch[0] + branch[branch.Count - 1])) //Is it cyclic?
{
cyclic++;
Console.WriteLine(" - This branch is cyclic! ");
}
else
{
Console.WriteLine();
}
for (int i = 0; i < max - 1; i++)
{
Console.Write(branch[i] + ",");
}
Console.WriteLine(branch[max - 1]);
}
}
}
c# math iteration np
asked Nov 19 at 11:42
Dutchottie
1
Speed up N(P) problem search - Sum-Square Problem
I was wondering if anyone could help me figuring out ways to speed up a small programm I was working on.
The problem is a math exercise called the Sum-Square Problem (https://youtu.be/G1m7goLCJDY).
So you take a list of continuous integers starting at 1 to N and see if you can reorder them so that the sum of each pair makes a square.
So for example:
1-3-6-10-15-
or
1-15-10-6-3-13-12-4-5-11-14-2-7-9-
The trick is to use all the numbers in the domain [1,N]. Obviously you can either find just one solution proving that there is a solution for [1,N] or you can show all the solutions for that domain. In the latter case you will get a reverse solution for each solution obviously, plus you can get so-called cyclic solutions where the start and end also make a square.
Now increasing N (after 23 there seems to be a solution for each N - not proven) exponentially increases the number of possible branches or paths you can try.
My program first was simple loops which checked basically every option. This meant my computer (simple i9 core) started to struggle (processing > 1h) at around N=30. I then changed method and first created a table or matrix containing only those numbers that would create a square for each number [1,N]. So for N=15 (first possible N with a solution) you would get:
For N=15 the squares possible are: 4, 9, 16, 25
1 - 3, 8, 15
2 - 7, 14
3 - 1, 6, 13
....
15 - 1, 10
I then traversed through this table to find possible solutions. If a path dead-ended the program backtracks until there is anpther branch, tries that one, backtracks, etc.
This took me up to about N=50 before it started taking too long (>1h) for my taste.
Up til then I was working with Lists (using C#) so I tried HashSets, that took it up to about N = 70. Now I seem to be stuck.
I either:
1) have to find another function that can process running through lists and paths faster, or
2) think of a completely different approach in mathematically solving this
3) step up the processing power
Does anyone have a smarter suggestion then the ones I thought of myself?
My code (C#):
using System;
using System.Collections.Generic;
namespace SumSquare
{
public class CalculateHash
{
List<List<int>> matrix = new List<List<int>>();
List<int> squares = new List<int>();
List<int> branch = new List<int>();
HashSet<int> defaultList = new HashSet<int>();
HashSet<int> worklist = new HashSet<int>();
int currentN, currentSet, currentIndex; //, prevIndex;
int max;
List<int> prevIndexSet = new List<int>(); //Holds prevSet index
bool going, going2;
DateTime startTime;
int successes = 0;
int cyclic = 0;
TimeSpan elapsed;
public void Calculate(int maxNum)
{
max = maxNum;
squares = FillSquares(max);
matrix = CreateMatrix(squares, max);
startTime = DateTime.Now;
for (int i = 1; i <= max; i++)
{
branch.Clear();
worklist.Clear();
branch.Add(i);
worklist = FillDefaultList(max);//Fill with all but current start number
worklist.Remove(i);
currentIndex = 0;
currentN = matrix[i][0]; //Get first element
currentSet = i; //remember current set, starting number
going = true;
while (going)
{
if (worklist.Contains(currentN))//Is this number still available?
{
branch.Add(currentN); //add currentN
worklist.Remove(currentN);//Clean up worklist
if (worklist.Count == 0) //All numbers processed! HIT
{
successes++;
ShowSucces();
//to quit at the first success
//going = false; //Quit at first success
//i = max + 1; //quit programm
}
prevIndexSet.Add(currentIndex);
currentSet = currentN;
currentN = matrix[currentSet][0];
currentIndex = 0;//reset for next Set
}
else //number already in use!
{
currentIndex++;
going2 = true;
if (currentIndex == matrix[currentSet].Count) //Used up all the numbers in this set?
{
while (going2)
{
int prevSet = branch[branch.Count - 1];//get the last number added at which this branch halted
branch.RemoveAt(branch.Count - 1); //remove this last number
//We need to add the number prevSet back into the workList BUT
//it needs to go at the correct location!! To keep the numbers in order
worklist.Add(prevSet); //Add the number back
if (branch.Count == 0) //We've exhausted all the possible paths starting with number (i)
{
going2 = false; //break out if this while
going = false; //break out of parent while
}
else
{
currentSet = branch[branch.Count - 1]; //Get the last number of the previous set
currentIndex = prevIndexSet[prevIndexSet.Count - 1] + 1; //Get the position in that set whee we last stopped and get the next position
prevIndexSet.RemoveAt(prevIndexSet.Count - 1);//remove that index reference
if (currentIndex < matrix[currentSet].Count) //No more numbers in this set
{
currentN = matrix[currentSet][currentIndex]; //carry on
going2 = false;
}
}
}
}
else
{
currentN = matrix[currentSet][currentIndex]; //Get the next number in this Set
}
}
}
}
TimeSpan elapsedTime = DateTime.Now - startTime;
Console.WriteLine("Time elapsed: " + elapsedTime.TotalSeconds);
Console.WriteLine("Number of successes: " + (successes * 0.5));
Console.WriteLine("Number of cyclic successes: " + cyclic);
Console.ReadKey();
}
List<List<int>> CreateMatrix(List<int> s, int m)
{
//This creates a 2-dimensional List, First dimension is [1,max], Second dimension the number need to get a sum when added to the current number
List<List<int>> t = new List<List<int>>();
t.Add(new List<int>()); //Element 0 is empty
for (int i = 1; i <= max; i++)
{
List<int> tt = new List<int>();
for (int j = 0; j < s.Count; j++)
{
int difference = s[j] - i;
if ((difference > 0) && (difference <= max) && difference != i) //Needs to be >0 and <=max
{
tt.Add(s[j] - i); //Now add the result: Square - currentINT
}
}
t.Add(tt); //Now stuff it into the parent List where INT=1 is Index=0
}
return t;
}
HashSet<int> FillDefaultList(int maxInt) //Fills a List with [1,max] integers
{
HashSet<int> l = new HashSet<int>();
for (int i = 1; i <= max; i++)
{
l.Add(i);
}
return l;
}
List<int> FillSquares(int max) //Creates a list of the squares of all values from [2,max] below the max + max-1 sum
{
List<int> l = new List<int>();
int maxSum = max + (max - 1);
for (int i = 2; i < max; i++)
{
if ((i * i) <= maxSum)
{
l.Add(i * i);
}
}
return l;
}
List<int> RemoveElement(List<int> list, int number)
{
List<int> l = new List<int>();
for (int i = 0; i < list.Count; i++)
{
if (list[i] != number)
{
l.Add(list[i]);
}
}
return l;
}
HashSet<int> FillWorklist(HashSet<int> defList, int cNum)
{
HashSet<int> l = defList;
l.Remove(cNum);
return l;
}
void ShowSucces()
{
Console.Write("Found a path with starting number: " + branch[0]);
if (squares.Contains(branch[0] + branch[branch.Count - 1])) //Is it cyclic?
{
cyclic++;
Console.WriteLine(" - This branch is cyclic! ");
}
else
{
Console.WriteLine();
}
for (int i = 0; i < max - 1; i++)
{
Console.Write(branch[i] + ",");
}
Console.WriteLine(branch[max - 1]);
}
}
}
c# math iteration np
c# math iteration np
asked Nov 19 at 11:42
Dutchottie
1
asked Nov 19 at 11:42
Dutchottie
1
asked Nov 19 at 11:42
Dutchottie
1
asked Nov 19 at 11:42
Dutchottie
1
asked Nov 19 at 11:42
Dutchottie
1
1
This may be better suited for cs.stackexchange.com
– Martin Wiboe
Nov 19 at 11:46
Let numbers (1,2,3...) be vertexes which are connected by edge if and only if the sum is a square (i.e.4and45are connected since4 + 45 == 49 == 7**2when3and8are not connected:3 + 8 == 11- not a square). So the initial task is a Hamiltonian Path Problem and you can try solving it with existing solvers. reference.wolfram.com/language/ref/FindHamiltonianPath.html
– Dmitry Bychenko
Nov 19 at 12:16
@Martin Wiboe: Thanks! I checked it and they primarily discuss if this is a true N(P) problem and not so much smart programming solutions.
– Dutchottie
Nov 20 at 12:16
@Dmitry Bychenko: Yes ofc you're correct. It is a special case of finding an Hamiltonian path. However as far as I know you can only solve this by brute force (and some smart avoiding using too much force). The question however remains: how to approach such a brute force with the least force - ie. the fastest processing?
– Dutchottie
Nov 20 at 12:16
add a comment |
This may be better suited for cs.stackexchange.com
– Martin Wiboe
Nov 19 at 11:46
Let numbers (1,2,3...) be vertexes which are connected by edge if and only if the sum is a square (i.e.4and45are connected since4 + 45 == 49 == 7**2when3and8are not connected:3 + 8 == 11- not a square). So the initial task is a Hamiltonian Path Problem and you can try solving it with existing solvers. reference.wolfram.com/language/ref/FindHamiltonianPath.html
– Dmitry Bychenko
Nov 19 at 12:16
@Martin Wiboe: Thanks! I checked it and they primarily discuss if this is a true N(P) problem and not so much smart programming solutions.
– Dutchottie
Nov 20 at 12:16
@Dmitry Bychenko: Yes ofc you're correct. It is a special case of finding an Hamiltonian path. However as far as I know you can only solve this by brute force (and some smart avoiding using too much force). The question however remains: how to approach such a brute force with the least force - ie. the fastest processing?
– Dutchottie
Nov 20 at 12:16
This may be better suited for cs.stackexchange.com
– Martin Wiboe
Nov 19 at 11:46
This may be better suited for cs.stackexchange.com
– Martin Wiboe
Nov 19 at 11:46
Let numbers (
1, 2, 3...) be vertexes which are connected by edge if and only if the sum is a square (i.e. 4 and 45 are connected since 4 + 45 == 49 == 7**2 when 3 and 8 are not connected: 3 + 8 == 11 - not a square). So the initial task is a Hamiltonian Path Problem and you can try solving it with existing solvers. reference.wolfram.com/language/ref/FindHamiltonianPath.html– Dmitry Bychenko
Nov 19 at 12:16
Let numbers (
1, 2, 3...) be vertexes which are connected by edge if and only if the sum is a square (i.e. 4 and 45 are connected since 4 + 45 == 49 == 7**2 when 3 and 8 are not connected: 3 + 8 == 11 - not a square). So the initial task is a Hamiltonian Path Problem and you can try solving it with existing solvers. reference.wolfram.com/language/ref/FindHamiltonianPath.html– Dmitry Bychenko
Nov 19 at 12:16
@Martin Wiboe: Thanks! I checked it and they primarily discuss if this is a true N(P) problem and not so much smart programming solutions.
– Dutchottie
Nov 20 at 12:16
@Martin Wiboe: Thanks! I checked it and they primarily discuss if this is a true N(P) problem and not so much smart programming solutions.
– Dutchottie
Nov 20 at 12:16
@Dmitry Bychenko: Yes ofc you're correct. It is a special case of finding an Hamiltonian path. However as far as I know you can only solve this by brute force (and some smart avoiding using too much force). The question however remains: how to approach such a brute force with the least force - ie. the fastest processing?
– Dutchottie
Nov 20 at 12:16
@Dmitry Bychenko: Yes ofc you're correct. It is a special case of finding an Hamiltonian path. However as far as I know you can only solve this by brute force (and some smart avoiding using too much force). The question however remains: how to approach such a brute force with the least force - ie. the fastest processing?
– Dutchottie
Nov 20 at 12:16
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53373904%2fspeed-up-np-problem-search-sum-square-problem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
This may be better suited for cs.stackexchange.com
– Martin Wiboe
Nov 19 at 11:46
Let numbers (
1,2,3...) be vertexes which are connected by edge if and only if the sum is a square (i.e.4and45are connected since4 + 45 == 49 == 7**2when3and8are not connected:3 + 8 == 11- not a square). So the initial task is a Hamiltonian Path Problem and you can try solving it with existing solvers. reference.wolfram.com/language/ref/FindHamiltonianPath.html– Dmitry Bychenko
Nov 19 at 12:16
@Martin Wiboe: Thanks! I checked it and they primarily discuss if this is a true N(P) problem and not so much smart programming solutions.
– Dutchottie
Nov 20 at 12:16
@Dmitry Bychenko: Yes ofc you're correct. It is a special case of finding an Hamiltonian path. However as far as I know you can only solve this by brute force (and some smart avoiding using too much force). The question however remains: how to approach such a brute force with the least force - ie. the fastest processing?
– Dutchottie
Nov 20 at 12:16