我试图安排的数字序列中的[1,2,3..n]任何两个相邻数字的这种序列中的总和加起来是一个素数 [英] Am trying to Arrange numbers in a sequence [1,2,3..n] such that sum of any 2 adjacent numbers in the sequence adds up to a prime number

问题描述

有关，例如：[1,2,3,4,5,6,7]可以设置为7,6,5,2,1,4,3

我试过数Permutaion，然后发现他们相邻的2号之和为质数，或者不使用Java。我得到了解决办法，但它需要长时间来执行。请提出你的想法。

下面

是code在努力。

 静态无效置换（java.util.List的＆LT;整数GT;编曲，整数k）{
    对于（INT I = K，I＆LT; arr.size（）;我++）{
                java.util.Collections.swap（ARR，I，K）;
                置换（ARR，K + 1）;
                java.util.Collections.swap（ARR，K，I）;
    }
    如果（K == arr.size（） -  1）{
        布尔isPrime = FALSE;
        对于（整数i = 0; I＆LT; arr.size（）;我++）{

            整数tmpIndex = 1 + 1;
            如果（tmpIndex＆其中; arr.size（））{
                整数primeSum = arr.get（ⅰ）+ arr.get（tmpIndex）;
                如果（isPrime（primeSum））{
                    isPrime = TRUE;
                } 其他 {
                    isPrime = FALSE;
                    打破;
                }
            }
        }
        如果（isPrime）{
            的System.out.println（匹配的值）;
            的System.out.println（java.util.Arrays.toString（arr.toArray（）））;
            System.exit（0）;
        }
    }
}
静态布尔isPrime（整数n）{
    的for（int i = 2; I＆LT; =的Math.sqrt（N）;我++）{
        如果（N％我== 0）
            返回false;
    }
    返回true;
}
 

解决方案

您下一步可能会产生排列一个简单的优化。即当给定一个置换preFIX像

  1，3，...
 

有没有必要检查所有其他成千上万的从1开始，3个选项，因为它们都将包含非相邻素数。

更新

下面是我的意思是在你的code：

 的（INT I = K，I＆LT; arr.size（）;我++）{
    java.util.Collections.swap（ARR，I，K）;
    如果（/ *对在位置（i  -  1，i）和在（I，I + 1）是素数* /）{
        置换（ARR，K + 1）;
    }
    java.util.Collections.swap（ARR，K，I）;
}
 

还有一个可能的优化是precalculating素数，并将其存储阵列进行快速检查。

for eg : [1,2,3,4,5,6,7] can be arranged as 7,6,5,2,1,4,3

I tried Permutaion of numbers and then finding their adjacent sum of 2 number is prime or not in Java. I get the solution but its taking long time for execution. Kindly suggest your ideas.

below is the code am trying.

static void permute(java.util.List<Integer> arr, Integer k) {
    for(int i = k; i < arr.size(); i++){
                java.util.Collections.swap(arr, i, k);
                permute(arr, k+1);
                java.util.Collections.swap(arr, k, i);
    }
    if (k == arr.size() - 1) {
        boolean isPrime = false;
        for (Integer i = 0; i < arr.size(); i++) {

            Integer tmpIndex = i + 1;
            if (tmpIndex < arr.size()) {
                Integer primeSum = arr.get(i) + arr.get(tmpIndex);
                if (isPrime(primeSum)) {
                    isPrime = true;
                } else {
                    isPrime = false;
                    break;
                }
            }
        }
        if (isPrime) {
            System.out.println("Matched Value");
            System.out.println(java.util.Arrays.toString(arr.toArray()));
            System.exit(0);
        }
    }
}
static boolean isPrime(Integer n) {
    for(int i=2; i<=Math.sqrt(n); i++){
        if (n % i == 0)
            return false;
    }
    return true;
}

解决方案

Your next step could be a simple optimization for generating permutations. I.e. when given a permutation prefix like

 1, 3, ...

There is no need to check all other thousands of options starting with 1, 3 as they all will contain a non-prime adjacent numbers.

UPDATE

Here is what I mean in your code:

for(int i = k; i < arr.size(); i++){
    java.util.Collections.swap(arr, i, k);
    if(/*pair at the position (i - 1, i) and at (i, i + 1) is prime*/){
        permute(arr, k+1);
    }
    java.util.Collections.swap(arr, k, i);
}

One more possible optimization is precalculating primes and storing them to array for quick checking.

这篇关于我试图安排的数字序列中的[1,2,3..n]任何两个相邻数字的这种序列中的总和加起来是一个素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！