HyperGraph
Changes
HyperGraph/Combinatorics.cs 85(+85 -0)
HyperGraph/HyperGraph.cs 30(+30 -0)
HyperGraph/HyperGraph.csproj 2(+2 -0)
HyperGraph/Program.cs 57(+46 -11)
Details
HyperGraph/Combinatorics.cs 85(+85 -0)
diff --git a/HyperGraph/Combinatorics.cs b/HyperGraph/Combinatorics.cs
new file mode 100644
index 0000000..a0f5fb7
--- /dev/null
+++ b/HyperGraph/Combinatorics.cs
@@ -0,0 +1,85 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HyperGraph
+{
+ static class Combinatorics<T>
+ {
+ /// <summary>
+ /// Множество перестановок (без повторения) элементов входящего множества
+ /// </summary>
+ /// <param name="array">Входящее множество</param>
+ /// <returns></returns>
+ public static List<List<T>> Transposition(List<T> array)
+ {
+ List<List<T>> result = new List<List<T>>();
+
+ int[] temp = new int[array.Count];
+ int n = array.Count;
+ for (int i = 0; i < n; i++)
+ temp[i] = i + 1;
+
+ while (true)
+ {
+ int j = n - 2;
+ while (j != -1 && temp[j] >= temp[j + 1])
+ j--;
+ if (j == -1)
+ break;
+
+ int k = n - 1;
+ while (temp[j] >= temp[k]) k--;
+
+ Swap(ref temp[j], ref temp[k]);
+ int l = j + 1, r = n - 1;
+ while (l < r)
+ Swap(ref temp[l++], ref temp[r--]);
+ result.Add(AddInOrderFromList(array, temp));
+ }
+
+ return result;
+ }
+ /// <summary>
+ /// Создает новый массив (лист) типа Т, со значениями в порядке массива order
+ /// </summary>
+ /// <param name="list">Лист значений</param>
+ /// <param name="order">Массив порядка значений</param>
+ /// <returns></returns>
+ private static List<T> AddInOrderFromList(List<T> list, int[] order)
+ {
+ List<T> temp = null;
+
+ try
+ {
+ temp = new List<T>();
+ for (int i = 0; i < order.Length; i++)
+ temp.Add(list[order[i] - 1]);
+ }
+ catch (Exception e)
+ {
+ Console.WriteLine(e.Message);
+ }
+ return temp;
+ }
+
+ private static bool Swap<t>(ref t a, ref t b)
+ {
+ try
+ {
+ t temp = a;
+ a = b;
+ b = temp;
+ }
+ catch (Exception e )
+ {
+ Console.WriteLine(e.Message);
+ return false;
+ }
+ return true;
+ }
+
+ }
+}
HyperGraph/HyperGraph.cs 30(+30 -0)
diff --git a/HyperGraph/HyperGraph.cs b/HyperGraph/HyperGraph.cs
new file mode 100644
index 0000000..43e9a94
--- /dev/null
+++ b/HyperGraph/HyperGraph.cs
@@ -0,0 +1,30 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HyperGraph
+{
+ class HyperGraph
+ {
+ public List<List<string>> HyperEdge;
+
+ public HyperGraph(Matrix<int> matrix)
+ {
+ HyperEdge = new List<List<string>>();
+
+ // По ребрам (столбцам)
+ for (int j = 0; j < matrix.countColumn; j++)
+ {
+ HyperEdge.Add(new List<string>());
+ // По вершинам (строкам)
+ for (int i = 0; i < matrix.countRow; i++)
+ {
+ if (matrix[i][j] == 1)
+ HyperEdge[j].Add("v" + i);
+ }
+ }
+ }
+ }
+}
HyperGraph/HyperGraph.csproj 2(+2 -0)
diff --git a/HyperGraph/HyperGraph.csproj b/HyperGraph/HyperGraph.csproj
index 25a2e26..37d2194 100644
--- a/HyperGraph/HyperGraph.csproj
+++ b/HyperGraph/HyperGraph.csproj
@@ -41,6 +41,8 @@
<Reference Include="System.Xml" />
</ItemGroup>
<ItemGroup>
+ <Compile Include="Combinatorics.cs" />
+ <Compile Include="HyperGraph.cs" />
<Compile Include="Matrix.cs" />
<Compile Include="Program.cs" />
<Compile Include="Properties\AssemblyInfo.cs" />
HyperGraph/Program.cs 57(+46 -11)
diff --git a/HyperGraph/Program.cs b/HyperGraph/Program.cs
index 76b6fee..0118ca8 100644
--- a/HyperGraph/Program.cs
+++ b/HyperGraph/Program.cs
@@ -8,24 +8,59 @@ namespace HyperGraph
{
class Program
{
+ /* 6 7
+ 0 0 1 0 1 0 0
+ 0 0 0 0 0 1 0
+ 1 1 1 0 0 0 0
+ 0 0 0 1 0 1 1
+ 0 1 1 1 0 0 0
+ 0 0 0 0 1 0 1
+ */
+
static void Main(string[] args)
- {
- Matrix<int> m = new Matrix<int>(4,5);
- List<int> ex = m[0];
- List<int> ex2 = m[2, true];
+ {
+ System.IO.StreamReader input = new System.IO.StreamReader("D:\\input.txt");
+ System.IO.StreamWriter output = new System.IO.StreamWriter("D:\\output.txt");
- List<int> ex3 = new List<int>(); ex3.Add(4); ex3.Add(5); ex3.Add(6); ex3.Add(7); ex3.Add(8);
- m[3] = ex3;
- List<int> ex4 = m[3];
+ // Экземпляр гипер-графа, созданный на основе загружаемой матрицы инцидентности
+ // 6 - кол-во строк, 7 - кол-во столбцов
+ HyperGraph graph = new HyperGraph(Matrix<int>.LoadFromStream(input, 6, 7));
+ // Массив (лист) всех возможных перестановок одного множества (гипер-ребра)
+ List<List<string>> transpos;
- System.IO.StreamReader input = new System.IO.StreamReader("D:\\input.txt");
- System.IO.StreamWriter output = new System.IO.StreamWriter("D:\\output.txt");
+ // Обработать все гипер-ребра
+ for (int i = 0; i < graph.HyperEdge.Count; i++)
+ {
+ // Получить массив перестановок текущего гипер-ребра
+ transpos = Combinatorics<string>.Transposition(graph.HyperEdge[i]);
+
+ // Вывод всех вершин текущего гипер-ребра
+ output.Write("Current edge include:");
+ for (int g = 0; g < graph.HyperEdge[i].Count; g++)
+ output.Write(" {0}", graph.HyperEdge[i][g]);
+
+ // Вывод всех перестановок текущего гипер-ребра
+ output.WriteLine();
- Matrix<int> matrix = Matrix<int>.LoadFromStream(input, 6, 7);
- Matrix<int>.UnloadToStream(matrix, output);
+ // Вывод начальной перестановки
+ output.Write("1:");
+ for (int g = 0; g < graph.HyperEdge[i].Count; g++)
+ output.Write(" {0}", graph.HyperEdge[i][g]);
+ output.WriteLine("\n\t-----------");
+ // Алгоритм перестановок не учитывает начальную, а начинает со следующей
+ for (int g = 0; g < transpos.Count; g++)
+ {
+ output.Write("{0}: ", g+2);
+ for (int f = 0; f < transpos[g].Count; f++)
+ output.Write("{0} ", transpos[g][f]);
+ output.WriteLine("\n\t-----------");
+ }
+ output.WriteLine();
+ }
input.Close(); output.Close();
+ Console.WriteLine("Completed. Press any key");
Console.ReadKey();
}
}