java - 是否可以设计一个递归来控制输出结果?

标签 java algorithm recursion

更新:我的问题在于从概念上理解如何实现它。例如(不像我下面的解决方案那么精确),我计算出列表中每个值的最大范围偏差,对于 5,3,2 可能是 4-6,2-4,1-3..I无法弄清楚如何处理该范围,因此我的递归仅处理该范围。我可以使用嵌套的 for 循环来做到这一点,但是递归有点棘手。

我的代码有两个部分在工作。一个生成值(递归地)和一个返回分数(我只关心超过特定阈值的解决方案)。两者都有效(见下面的代码)。问题在于整合它们,因为我意识到我不能简单地引用控制它的方法,因为递归仍然会产生很多结果。我想我需要更改我的递归代码,以某种方式合并我的类似方法(返回分数的方法)的逻辑。

递归方法采用一个列表和一个整数,并尝试找出所有可以将总和中的值相乘以等于总和的唯一方式(如果您发送一个值列表,5,3,2 和一个目标100的总和。计算公式是5x + 3y + 2z = 100,求解x,y和z的所有可能值。这是在下面的示例代码,如果您运行它,您将获得完整的结果集)。我的问题是我不需要大部分结果,只需要符合某些特征的结果。我创建了一个方法(并计划创建更多)来限制结果,但我不确定如何设计递归方法来节省时间而不计算我不需要的结果。

这是基于一小部分结果的示例输出。目前,我得到所有结果,然后过滤并删除特定结果,但这意味着我首先必须创建一个非常大的数据集(其中大部分我不需要)。这是一个可能的输出(不是完整的输出,因为结果太多,我手动执行此操作):

Initial list of values [5, 3, 2]
initial list of quantities: [6.0, 8.0, 23.0]. 

// (5*6)+(3*8)+(2*23)=100 as do all examples below but I only want to include 
//the ones with scores above 90(see similar method in my code to see how I get this score)  

[0.0, 0.0, 50.0] // score = 0.7120763990222406 < -- should not be included
[0.0, 2.0, 47.0] // score = 0.7454415587728428 < -- should not be included
[1.0, 11.0, 31.0] // score = 0.9010050506338834 < -- should be included
[1.0, 13.0, 28.0] // score = 0.9133974596215562 < -- should be included
[1.0, 29.0, 4.0] // score = 0.7124239231090319 < -- should not be included

我想找出一种方法来避免生成不应该包含的那些,首先。

希望这是有道理的。这是代码(第一个方法,findVariables,使用列表/求和生成结果,第二个,similar,是一个我不知道的控制函数的例子如何整合)。如果我没有正确解释它,我认为回顾这两种方法将使我在做的事情变得清晰。

导入java.util.ArrayList; 导入 java.util.Arrays; 导入 java.util.HashMap; 导入 java.util.Iterator; 导入java.util.List; 导入 java.util.Map; 导入 java.util.Map.Entry;

公共(public)类查找变量{

public static void findVariables(double[] constants, double sum, ArrayList<ArrayList<Integer>> ranges) {
    findVariables0(constants, sum, new double[constants.length], 0, ranges);
}

private static void findVariables0(double[] constants, double remaining, double[] variables, int n, ArrayList<ArrayList<Integer>> ranges) {
    //System.out.println();
    if(n == constants.length - 1) {
        // solution if the remaining is divisible by the last constant.
        if (remaining % constants[n] == 0) {
            variables[n] = remaining/constants[n];
            System.out.println(Arrays.toString(variables));
        }
    } else {
        for (int i = ranges.get(n).get(0), limit = (int) (remaining/constants[n]); i <= ranges.get(n).get(1); i++) {
            variables[n] = i;
            findVariables0(constants, remaining - i * constants[n], variables, n+1, ranges);
        }
    }
}

private static void similar(HashMap<String, Integer> list1, HashMap<String, Integer> list2) {

    //TODO: This is currently Euclidean Distance, change it to pearson score as it protects from grade inflation, same logic
    //TODO: assess the logic here.  My logic is all the sums are the same, then I can get an accurate difference by simply studying the differences in values they in common
    System.out.println("hello from simlair method. Hopefully I don't crash or worst..turn evil :-)");
    double runsum = 0.0;
    List<String> keys_in_common = new ArrayList<String>();
    for (Entry<String, Integer> entry : list1.entrySet())
    {
        String key = entry.getKey();
        if (list2.containsKey(key)) {
            keys_in_common.add(key);
        }
    }

    Iterator it=keys_in_common.iterator();

    while(it.hasNext())
    {
      String value=(String)it.next();

      //System.out.println("Value :"+value);
      runsum += Math.pow((list1.get(value) - list2.get(value)),2);
      //System.out.println(runsum);
    }
    double score = Math.pow(runsum, .5);
    double score_percent = (100-score)*.01;
    System.out.println(score_percent);


}

public static void main(String... args) {
    HashMap<String, Integer> list1 = new HashMap<String, Integer>();
    HashMap<String, Integer> list2 = new HashMap<String, Integer>();
    list1.put("a", 5);
    list1.put("b", 3);
    list1.put("c", 2);

    list2.put("a", 3);
    list2.put("b", 3);
    list2.put("c", 2);

    //Trying to capture the range around [6.0, 8.0, 23.0] so creating a list of list of values to keep within the range
    ArrayList<ArrayList<Integer>> listOlists = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> singleList1 = new ArrayList<Integer>();
    singleList1.add(4);
    singleList1.add(8);
    listOlists.add(singleList1);
    ArrayList<Integer> singleList2 = new ArrayList<Integer>();
    singleList2.add(6);
    singleList2.add(10);
    listOlists.add(singleList2);
    ArrayList<Integer> singleList3 = new ArrayList<Integer>();
    singleList3.add(20);
    singleList3.add(25);
    listOlists.add(singleList3);

    System.out.println(listOlists);

    similar(list1, list2);
    findVariables(new double[]{5, 3, 2}, 100, listOlists);

}

我的最终目标是拥有几千个总和较大的变量,并使用类似这样的各种方法来控制结果不会太大。

谢谢!另外,如前所述,我对 Java 非常陌生,而且我确信我在犯错误。我欢迎有关如何改进的提示和建议。你可以看到我想要的输出和我当前的代码,但我非常乐意改变我的整个方法,如果更好的话,所以不要觉得你的建议需要在我现有代码的上下文中..

最佳答案

编辑

离开我们的评论,这是一个想法:

将成对列表作为参数添加到您的 findVariables0 函数中,将范围作为两个值 - 例如

(4,6)

表示 4-6 的范围 - 让我们称列表为“范围”。在循环中

        for (int i = 0, limit = (int) (remaining/constants[n]); i <= limit; i++) {
            variables[n] = i;
            findVariables0(constants, remaining - i * constants[n], variables, n+1);
        }

设置

i = ranges[n].getFirst();" // should be (4)

并添加条件值

&& i < ranges[n].getSecond(); i++) // should be 6

这应该将您的递归限制在您想要的范围内。

结束编辑

据我所知,您现在在代码中所说的是:

  • 得到n个变量的多项式的所有可能解;
  • 从这组解决方案中,选择几何上接近我提供的点的解决方案。

并且您想将第二个语句合并到第一个语句中,说:

  • 查看我提供的一个点,并获得接近该点的多项式的解。

如果不是,那我理解错了。

如果我问你,那么:因为 - 至少,在你当前的代码中 - 无论如何你都会运行所有的解决方案,你可能想要查看而不是生成靠近你的 HashMaps 列表建议 HashMap,然后检查所有这些。根据您对“接近”的定义,这可能会减少很多额外的可能性,因为(如果我没记错的话)一个总和为 100 的 3 多项式解有 100^3 种不同的可能性,而 90% 的 100 ^3 很多 - 尽管您在当前代码中使用“remaining/constants[n]”行删除了很多它们,但做得很好。

遗憾的是,我的数学方面不够好,无法帮助您制定精确的算法,但我希望我已经让您走上了通往算法的道路。请记住,您可能无法让所有优化都与其他优化一起发挥作用,因此您可能不得不最终在一些优化之间做出选择,而不是在其他优化之间做出选择。

好的,我还有一些其他注意事项希望能有所帮助:

除了你“得分”的地方,我真的不认为有必要把所有东西都变成双倍的——有一次你做除法,你无论如何都把它当作一个整数,所以最好把它们做成所有整数,我想 - 节省内存等等。

为什么要将数组传递给“相似”的 HashMap?您基本上像数组一样遍历它们,并且您将始终比较相同大小的列表(对吗?我可能会误解),因此无需经历使用键存储数据然后将其取出的额外麻烦再次按顺序运行所有键。

看得更清楚了

runsum += Math.pow((list1[n] - list2.get[n]),2);

比所有的 HashMapstuff - 而且它仍然是 O1 访问时间。我不确定将它们存储在 HashMaps 中对你有什么帮助。

祝你好运!希望我有所帮助。

关于java - 是否可以设计一个递归来控制输出结果?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9644101/

相关文章:

c++ - 围绕点的最小凸多边形

c# - 无法理解ID3算法

c - C中快速高效的最小二乘拟合算法?

recursion - ViewAttributes 递归范围不起作用 SharePoint 2013 CAML 查询以递归方式从文档库中获取所有文件

java - 递归查找链表的最大值

c - C中的二项式系数递归解

java - 我很困惑。插入排序(基本排序,我知道)算法正在做一些我无法解释的事情

java - java.util.Properties 中的多个值

java - 从链表中删除集合的方法

java - 什么是 NullPointerException,我该如何解决?