求助集合划分算法
例如,字符串“25482”,
如果按1组来分需要得到如下结果:
x25482
如果按2组来分得到如下结果:
x2548x2,
x254x82,
x25x482,
x2x5482
如果按3组来分需要得到如下结果:
x254x8x2,
x25x4x82,
x25x48x2,
x2x5x482,
x2x45,x82,
x2x548x2
不能乱序。
------解决方案--------------------
static public Collection<string> Divid(string S, int Count)
{
//S: 要分的字符串;
//Count: 要分的组数
if (Count < 1 || Count > S.Length)
return null;
Collection<string> Result = new Collection<string>();
if (Count == 1)
{
Result.Add("x" + S);
return Result;
}
int L = S.Length;
int[] Pos = new int[Count + 1]; // 'x' 插入的位置,多加一个位置以便编程
for (int i = 0; i < Count; i++)
Pos[i] = i;
Pos[Count] = L;
for (; ; )
{
string R = "";
for (int i = 0; i < Count; i++)
R += "x" + S.Substring(Pos[i], Pos[i + 1] - Pos[i]);
Result.Add(R);
for (int i = 1; i < Count; i++) //检查有没有可以往后移动的
{
if (Pos[i + 1] - Pos[i] >= 2)
{ //有
Pos[i]++;
for(int j = 1; j<i; j++) //这两行是新增加的
Pos[j] = j; //
goto hesNext; //跳转到外层循环的Continue前面继续循环;
}
}
break; //没有了
hesNext: continue;
}
return Result;
}
------解决方案--------------------
C# code
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
string s = "25482";
int n = 2;
var data = Enumerable.Range(1, s.Length - 1);
IEnumerable<int[]> query = data.Select(x => new int[] { x });
for (int i = 1; i < n; i++)
{
query = query.SelectMany(x => data.Select(y => x.Concat(new int[] { y }).ToArray()));
}
query = query
.Select(x => x.OrderBy(y => y).Distinct().ToArray())
.Where(x => x.Count() == n - 1)
.OrderByDescending(x => string.Join(",", x))
.GroupBy(x => string.Join(",", x))
.Select(x => x.First())
.Select(x => new int[] { 0 }.Concat(x).ToArray());
foreach (var item in query)
{
Console.WriteLine(string.Join("", s.Select((x, i) => item.Contains(i) ? "x" + x : x.ToString())));
}
}
}
}