求简单算法

Question

2个整数集合，1个Count少，1个Count多，但2集合的Sum相等。
想对2集合配对。求算法。举例 : 集合1:   5,8
集合2:   2,2,2,3,4配对结果:
         5=2+3
         6=2+2+4注: 集合1的数据不会拆分。

Answer 1

没太看懂楼主意思，这样么？static void Main(string[] args)
{
    int[] a1 = { 5, 8 };
    int[] a2 = { 2, 2, 2, 3, 4 };
    if (Yes(a1, a2)) Console.WriteLine("符合楼主要求");
    Console.ReadKey();
}public static bool Yes(int[] a1, int[] a2)
{
    return a1.Length != a2.Length && a1.Sum() == a2.Sum();
}

Answer 2

static void Main(string[] args)
{
    int[] a1 = { 5, 8 };
    int[] a2 = { 2, 2, 2, 3, 4 };
    if (Yes(a1, a2)) Console.WriteLine("符合楼主要求");
    Console.ReadKey();
}
public static bool Yes(int[] a1, int[] a2)
{
    return a1.Length != a2.Length && a1.Sum() == a2.Sum();
}[/Quote]谢谢。
a1.Length != a2.Length && a1.Sum() == a2.Sum(); 这2点是前提，不用在判断了。

Answer 3

2个集合既然已经符合规则，还怎么配对？还是说多个int[]的交错数组中。找到2个或多个长度不同，但求和相同的？

Answer 4

0.0
LS的童鞋V5..测试可行..

Answer 5

看明白了。写个实现，不快，也不易读。因为写了，还是贴来吧。static void Main(string[] args)
{
    int[] a1 = { 5, 8 };
    int[] a2 = { 2, 2, 2, 3, 4 };
    Func<List<int>, List<List<int>>> GetArrays = null;
    GetArrays = arr =>
        {
            List<List<int>> result = new List<List<int>>();
            if (arr.Count>2)
            {
                for (int i = 0; i < arr.Count; i++)
                {
                    List<int> temp = new List<int>(arr);
                    temp.RemoveAt(i);
                    //if (arr.Count == 2) break;
                    result.AddRange(GetArrays(temp));
                }                        
            }
            result.Add(arr);
            return result;
        };
    Func<List<int>, List<int>, bool> IsSameList = (x, y) =>
        {
            if (x.Count != y.Count) return false;
            for (int i = 0; i < x.Count; i++)
            {
                if (x[i] != y[i]) return false;
            }
            return true;
        };
    List<List<int>> all = GetArrays(new List<int>(a2));
    List<List<int>> items = new List<List<int>>();
    foreach (List<int> item in all)
    {
        bool same = false;
        foreach (List<int> item2 in items)
        {
            if(IsSameList(item,item2))
            {
                same=true;
                break;
            }
        }
        if (!same) items.Add(item);
    }
    for (int index = 0; index < a1.Length; index++)//循环a1
    {
        foreach (List<int> item in items)
        {
            if (a1[index] == item.Sum())
            {
                Console.Write(a1[index].ToString() + "=");
                for (int i = 0; i < item.Count; i++)
                {
                    Console.Write(item[i]);
                    if (i < item.Count - 1) Console.Write("+");
                }
                Console.WriteLine();
            }
        }
    }
            
    Console.ReadKey();
}

Answer 6

晕，csdn的过滤规则到底是啥啊。换行空格也过滤？？

Answer 7

static void Main(string[] args)
{
    //声明数组
    int[] a1 = { 5, 8 };
    int[] a2 = { 2, 2, 2, 3, 4 };
    //声明一个匿名函数
    Func<List<int>, List<List<int>>> GetArrays = null;
    //使用Lambda实现一个匿名的递归函数
    GetArrays = arr =>
    {
        //每次递归创建一个临时的list保存当次结果
        List<List<int>> result = new List<List<int>>();
        //如果需要排列组合的数据超过2个元素则递归添加
        if (arr.Count > 2)
        {
            //当前数组，每次移除一个字符得到一个新数组，递归的调用GetArrays方法获取新数组的排列组合
            for (int i = 0; i < arr.Count; i++)
            {
                List<int> temp = new List<int>(arr);
                temp.RemoveAt(i);
                result.AddRange(GetArrays(temp));
            }
        }
        //将当前的数组添加
        result.Add(arr);
        return result;//返回当前数组的所有排列组合
    };
    //匿名函数，实现两个List的判断
    Func<List<int>, List<int>, bool> IsSameList = (x, y) =>
    {
        if (x.Count != y.Count) return false;
        for (int i = 0; i < x.Count; i++)
        {
            if (x[i] != y[i]) return false;
        }
        return true;
    };
    //获取所有排列组合
    List<List<int>> all = GetArrays(new List<int>(a2));
    //定义一个过滤后的组合列表
    List<List<int>> items = new List<List<int>>();
    //依次判断，避免添加重复的组合，因为元数据中的2有多个，可能排列出来会有重复项，还很多。
    foreach (List<int> item in all)
    {
        bool same = false;
        foreach (List<int> item2 in items)
        {
            if (IsSameList(item, item2))
            {
                same = true;
                break;
            }
        }
        if (!same) items.Add(item);
    }
    //循环a1，检查结果
    for (int index = 0; index < a1.Length; index++)//循环a1
    {
        //循环排列组合队列，检查是否相加的和与a1的某个元素相等
        foreach (List<int> item in items)
        {
            if (a1[index] == item.Sum())//linq求和比较
            {
                //输出结果
                Console.Write(a1[index].ToString() + "=");
                for (int i = 0; i < item.Count; i++)
                {
                    Console.Write(item[i]);
                    if (i < item.Count - 1) Console.Write("+");
                }
                Console.WriteLine();
            }
        }
    }    Console.ReadKey();
}
因为觉得排列组合那块效率不高。就没打算写注释。你想看，就写给你好了。参考一下。

Answer 8

这个算法有点问题，如果是
    int[] a1 = { 5, 8 ,12};
    int[] a2 = { 2, 2, 2, 3, 4 ,6, 6};
的情况，会出现冗余组合
其实只有一种
结果是
5=2+3
8=2+2+4
12=6+6

Answer 9

sorry，那是我没说明白吧

Answer 10

肯定是NP的，即使确定有解，也只能在小数据量中求解，问一下LZ两组的数据量大概有多大？
超过64个的话，状态压缩的Hash都不好设计！

Answer 11

LZ解决了吗？
42楼说的对，NP是有的，而且还不止1次会调用，想想
数据量大的话，肯定不行。

Answer 12

debug了一下，这样会产生很多冗余数据，增加了算法负担。
改进一下应该可以。
先整理一下思路，争取周末coding。1.大集合进行排列组合，取出可能的组合。 
2.对组合的Sum，和小集合的value比较，再进行分组。 
3.过滤值重复利用的组合。
4.组后还是多集合，任选一项。如果用同一个NP解决所有分组，效率会大大提高。感觉能出来，继续思考中

Answer 13

class Program
{
static void Main(string[] args)
{
int[] a1 = { 5, 8 };
int[] a2 = { 2, 2, 2, 3, 4 };
List<List<int>> results = new List<List<int>>(new List<int>[] { new List<int>() }); if (CheckSet(a1, a2, results))
{
foreach (List<int> r in results)
{
if (r.Count > 0)
{
Console.Write(r[0] + "=");
Console.WriteLine(string.Join("+", r.ConvertAll(i => i.ToString()).ToArray(), 1, r.Count - 1));
}
}
}
else
Console.WriteLine("结果不匹配");
Console.ReadKey();
} static bool CheckSet(int[] a1, int[] a2, List<List<int>> results)
{
int i = Array.FindIndex(a1, v => v != 0);
if (i == -1)
return Array.FindIndex(a2, v => v != 0) == -1; List<int> lastResult = results[results.Count - 1];
if (lastResult.Count == 0)
lastResult.Add(a1[i]); for (int j = 0; j < a2.Length; j++)
{
if (a2[j] > 0 && a2[j] <= a1[i])
{
int v = a2[j];
a1[i] -= v;
a2[j] = 0;
lastResult.Add(v);
if (a1[i] == 0)
results.Add(new List<int>()); if (CheckSet(a1, a2, results))
{
return true;
}
lastResult.RemoveAt(lastResult.Count - 1);
a1[i] += v;
a2[j] = v;
}
}
return false;
}}

Answer 14

LZ在33#楼说的：
这个算法有点问题，如果是
  int[] a1 = { 5, 8 ,12};
  int[] a2 = { 2, 2, 2, 3, 4 ,6, 6};
的情况，会出现冗余组合
其实只有一种
结果是
5=2+3
8=2+2+4
12=6+6但是其实还有一种配对：
5=2+3 8=2+6 12=6+2+4
我不知道是不是lZ想找出上面说的所有的或者是最优（这个应该不是~~）的或者不存在配对呢？是不是 想的简单了？前提的一部分是 和等 容量不等，称作前提1
{1,2,3,4}       {3,3,4}  集合A
{2,2,2,2，2}     {8,2}   集合B
这样呢 配对规则是什么呢？
那就按楼主说的不符合前提（前提2），两个集合不是“不会拆分”不被纳入考虑。
前提2会把符合前提1集合对排除掉多少？
我其实要说的是 如果A，B符合前提 只要根据A的元素Ai从集合B寻找配对{Bi}甚至可以按照顺序来 可以找到一个解；
看这样分析如果A集合只有一个元素，显然成立；
如果A有2元素，有前提2，A1必然可以找到{B1}；而再有前提1,剩下的{B2}就是A2的；然后用递推吧没时间了 反正我的结论就是只要有一个找不到配对 这个就是无解的；
然后要找所有解 就是对B集合进行分析 这个可能才是重点

Answer 15

这个方法很巧，谢谢。
但是有个问题，默认是从小到大的配对，如果有多配对且，前面配对错误的话，结果就不对了。
例如 int[] a1 = { 6, 7 ,10 };
 int[] a2 = { 1, 2, 3, 4, 5, 8};配对结果应该是
6=1+5;
7=3+4;
10=2+8;但是这个方法的结果却不是这样的。

Answer 16

嗯，是的，忘了清理递归失败时记录的无效数据
在最一句 returned false; 的前面再加一句：
if (lastResult.Count <= 1)
results.RemoveAt(results.Count-1);
return false;