baran
While I was checking my old machine, I found out a “great” implementation.
Given the two lists:
List1 List2
1 3
2 3
3 6
4 5
5 2
6 2
7 9
9 11
10 1
11 13
13 14
14 12
15 19
17 18
19 20
20 16
21 22
22 21
23 23
24 23
I need to grab the conditions similar to the following:
1 4, 4 6, 6 1
2 3, 3 5, 5 2
Well, let me iterate on the case:
In fact the lists are just the extraction of a table record of an MSSQL database, Both lists are indicating the columns which form a composite key.
The list1 is incremental and a row may be deleted by the user.
a b c d e f g h
List1: 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 19, 20, 21, 22, 23, 24
List2: 3, 3, 6, 5, 2, 2, 9, 11, 1, 13, 14, 12, 19, 18, 20, 16, 22, 21, 23, 23
Given the lists above:
1 3 3 6 6 6 2 is not forming a loop, (a, c, f) You cannot go back as 2 6 (which is b), you have to go forward, and the output of the program should be the first row which is 1 3(a)
2 3 3 6 6 2 is another loop (b, c, f) and the output of the program should be as 2 3
3 6 6 2 is another loop but a loop within loop, so it shouldn’t be outputted.
4 5 5 2 is not a loop
7 9 9 11 11 13 13 14 14 12 is not a loop
15 19 19 20 20 16 is not a loop
21 22 22 21 is a loop
23 23 is a loop
23 23 24 23 is another loop (not an inner loop as it’s different than above, 23 23). These loops or cycles had a special meaning in discrete maths, hamiltonian cycle maybe? I will check that later. The following is the solution for the case.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
private static List List1 = new List { 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 19, 20, 21, 22, 23, 24 };
private static List List2 = new List { 3, 3, 6, 5, 2, 2, 9, 11, 1, 13, 14, 12, 19, 18, 20, 16, 22, 21, 23, 23 };
static void Main(string[] args)
{
Dictionary<string, Sequence> Sequences = new Dictionary<string, Sequence>();
Sequence sq;
for (int i = 1; i < List1.Count; i++)
{
sq = GenerateSequence(List1[i]);
if (sq != null)
{
if (!Sequences.ContainsKey(sq.StartingPair.ToString()))
{
Sequences.Add(sq.StartingPair.ToString(), sq);
}
}
}
Console.WriteLine("Unique Sequences:");
foreach (KeyValuePair<string, Sequence> UniqueLoop in Sequences)
{
Console.WriteLine("Starts with: " + UniqueLoop.Key.ToString() + " | Sequence: " + UniqueLoop.Value.ToString());
}
Console.WriteLine("");
Console.Write("Press Enter to Quit");
Console.ReadLine();
}
private static Sequence GenerateSequence(int StartingValue)
{
List sequence = new List();
int counter = 0;
int Value = StartingValue;
int NextValue;
int NextValueIndex;
do
{
NextValueIndex = List1.IndexOf(Value);
if (NextValueIndex != -1)
{
NextValue = List2[NextValueIndex];
if (NextValue >= Value)
{
sequence.Add(new SequencePair(Value, NextValue));
Value = NextValue;
}
else
{
foreach (SequencePair sp in sequence)
{
if (sp.value1 == NextValue)
{
// we found a loop!
sequence.Add(new SequencePair(Value, NextValue));
return new Sequence(sequence);
}
}
return null;
}
}
else
{
return null;
}
counter++;
} while (Value != StartingValue && counter < List2.Count);
return new Sequence(sequence);
}
}
public class Sequence
{
public SequencePair StartingPair = null;
public List Pairs;
public Sequence(List Pairs)
{
this.Pairs = Pairs;
foreach (SequencePair sp in Pairs)
{
if (this.StartingPair == null || sp.value1 < StartingPair.value1)
{
this.StartingPair = sp;
}
}
Output of above program is as follows:
Unique Sequences: Starts with: 2 3 | Sequence: 2 3, 3 6, 6 2 Starts with: 21 22 | Sequence: 21 22, 22 21 Starts with: 23 23 | Sequence: 23 23 Press Enter to Quit
