Skip to content

Instantly share code, notes, and snippets.

@wyanez
Last active February 28, 2019 07:17
Show Gist options
  • Save wyanez/1e62ecf95eb114ed86de26e750f656de to your computer and use it in GitHub Desktop.
Save wyanez/1e62ecf95eb114ed86de26e750f656de to your computer and use it in GitHub Desktop.
Obtener las combinaciones de k números un conjunto de datos que sumen t.
<Project Sdk="Microsoft.NET.Sdk">
<PropertyGroup>
<OutputType>Exe</OutputType>
<TargetFramework>netcoreapp2.2</TargetFramework>
</PropertyGroup>
<ItemGroup>
<PackageReference Include="ExcelDataReader" Version="3.4.2" />
<PackageReference Include="System.Text.Encoding.CodePages" Version="4.5.1" />
</ItemGroup>
</Project>
using System;
using System.IO;
using ExcelDataReader;
using System.Text;
using System.Collections.Generic;
using System.Data;
namespace KCombinaciones
{
class MyExcelReader
{
public static double[] processDataFromXls(string filePath)
{
//System.Text.Encoding.RegisterProvider(System.Text.CodePagesEncodingProvider.Instance);
List<double> dataAux = new List<double>();
int contRows = 0;
using (var stream = File.Open(filePath, FileMode.Open, FileAccess.Read)) {
// Auto-detect format, supports:
// - Binary Excel files (2.0-2003 format; *.xls)
// - OpenXml Excel files (2007 format; *.xlsx)
using (var reader = ExcelReaderFactory.CreateReader(stream)) {
do {
while (reader.Read()) {
double value = reader.GetDouble(0);
dataAux.Add(value);
contRows++;
}
break; //Para procesar solo la hoja1
} while (reader.NextResult());
}
}
Console.WriteLine("Procesado {0} Leidas {1} Filas",filePath,contRows);
return dataAux.ToArray();
}
public static List<KInstance> processDataMultipleFromXls(string filePath)
{
//System.Text.Encoding.RegisterProvider(System.Text.CodePagesEncodingProvider.Instance);
List<KInstance> dataAux = new List<KInstance>();
using (var stream = File.Open(filePath, FileMode.Open, FileAccess.Read))
{
using (var reader = ExcelReaderFactory.CreateReader(stream))
{
var result = reader.AsDataSet();
DataTable table = result.Tables[0];
for (var i = 1; i < table.Rows.Count; i++)
{
KInstance aux;
aux.k = Convert.ToInt32(table.Rows[i][0]);
aux.t = Convert.ToDouble(table.Rows[i][1]);
string dataStr = (string) table.Rows[i][2];
string[] data = dataStr.Split(",");
aux.data = new double[data.Length];
//Console.WriteLine("{0}: k={1} t={2}",i,aux.k,aux.t);
//Console.Write("data({0}) = ",data.Length);
for (int j = 0; j < data.Length; j++)
{
aux.data[j] = Convert.ToDouble(data[j].Replace('.',','));
//Console.Write("{0} ",aux.data[j]);
}
//Console.WriteLine();
dataAux.Add(aux);
}
}
}
Console.WriteLine("Leidos {0} Casos",dataAux.Count);
return dataAux;
}
}
struct KInstance
{
public int k;
public double t;
public double[] data;
}
}
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
namespace KCombinaciones
{
class Program
{
static double[] data;
static int contSol=0;
static int contComb=0;
static double[] sol;
static string outputFileName;
static List<double[]> solutions;
static double sumSolutions = 0;
static void Main(string[] args)
{
//doProcessSingleCase();
doProcessMultipleCase();
Console.WriteLine("Presione una tecla para salir...");
Console.Read();
}
private static void doProcessMultipleCase()
{
//string dataExcelInput = "ToTestCode.xlsx";
string dataExcelInput = "D:\\VisualStudio\\KCombinaciones\\ToTestCode.xlsx";
List<KInstance> dataInput = MyExcelReader.processDataMultipleFromXls(dataExcelInput);
int numCase = 1;
foreach(var kInstance in dataInput){
data = kInstance.data;
Console.WriteLine("{0}: k={1} t={2} data({3}) = ",numCase,kInstance.k,kInstance.t,data.Length);
Array.Sort(data,new ReverseComparer());
//for (int j = 0; j < data.Length; j++)
// Console.Write("{0} ",data[j]);
//Console.WriteLine();
doSingleKProcess(kInstance.k,kInstance.t,numCase);
numCase++;
}
}
static void doProcessSingleCase(){
//string dataExcelInput = "data.xlsx";
string dataExcelInput = "D:\\VisualStudio\\Combinaciones\\data.xlsx";
data = MyExcelReader.processDataFromXls(dataExcelInput);
Array.Sort(data,new ReverseComparer());
double t = 615.84;
//double t = 1220.75;
//int k = 5;
//doSingleKProcess(k,t);
doMultipleKProcess(15,t);
}
static void doMultipleKProcess(int limit, double t)
{
for (int k = 3; k <=limit; k++)
{
doSingleKProcess(k,t,k);
}
}
static void doSingleKProcess(int k, double t, int numCase){
sol=new double[k];
solutions =new List<double[]>();
sumSolutions = 0;
outputFileName = "C:\\Salida_case_"+ numCase.ToString() +".txt";
//outputFileName = "Salida_case_"+ numCase.ToString() +".txt";
var watch = new System.Diagnostics.Stopwatch();
watch.Start();
using (StreamWriter fileSalida = new StreamWriter(outputFileName)){
fileSalida.WriteLine("Combinaciones para K={0} y T={1}",k,t);
combinar(0,0,k,t);
processSolution(k,fileSalida);
fileSalida.WriteLine("Encontradas {0} Combinaciones con k={1} y sum ={2}",contSol,k,t);
fileSalida.WriteLine("Total {0} Combinaciones con k={1}",contComb,k);
}
watch.Stop();
Console.WriteLine("Proceso Finalizado para k={0} => {2} Combinaciones encontradas. Salida enviada a {3}. Tiempo: {1} ms",k,watch.ElapsedMilliseconds,contSol,outputFileName);
}
static void combinar(int nsol, int i, int k, double t)
{
if(nsol==k){
double sum = sumSolutions;
if(Math.Abs(sum-t)<0.0001){
double[] auxSol = new double[k];
Array.Copy(sol,auxSol,k);
solutions.Add(auxSol);
}
contComb++;
nsol--;
return;
}
for (int j = i; j < data.Length; j++)
{
sol[nsol]=data[j];
sumSolutions += data[j];
if(sumSolutions-t<0.0001){
combinar(nsol+1,j+1,k,t);
}
sumSolutions -= data[j];
}
}
private static void processSolution(int k, StreamWriter fileSalida)
{
solutions.Sort(sortList);
List<double[]> lComb = new List<double[]>();
double[] lastList = null;
foreach (var lista in solutions)
{
if(lastList==null || sortList(lista,lastList) != 0 ){
if(lastList==null) lastList= new double[k];
Array.Copy(lista,lastList,k);
lComb.Add(lista);
}
}
printSolutions(lComb,fileSalida);
}
private static int sortList(double[] l1, double[] l2) {
if(l1.Length == l2.Length){
int res=0;
for (int i = 0; i < l1.Length; i++)
{
res = l1[i].CompareTo(l2[i]);
if(res!=0) break;
}
return res;
}
else return l1.Length.CompareTo(l2.Length);
}
private static void printSolutions(List<double[]> lComb, StreamWriter fileSalida)
{
contSol = 0;
foreach (var lsol in lComb)
{
fileSalida.Write("{0})[",++contSol);
for (int i = 0; i < lsol.Length; i++)
{
fileSalida.Write("{0}",lsol[i]);
if(i<lsol.Length-1) fileSalida.Write(" ");
}
fileSalida.WriteLine("]");
}
}
}
public class ReverseComparer : IComparer
{
public int Compare(Object x, Object y)
{
return Comparer.Default.Compare(y, x );
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment