`
爱宝贝丶
  • 浏览: 7411 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

使用三种方法求解前N个正整数的排列

阅读更多

       本篇博文给大家介绍前N个正整数的排列求解的三种方式。第一种是暴力求解法;第二种则另外声明了一个长度为N的数组,并且将已经排列过的数字保存其中;第三种方式则采用了另外一种思路,即首先获取N个整数的升序排列,然后对其位置进行随机交换以达到前N个整数的随机排列的目的。首先我们来看看第一种方式,具体代码如下:

import java.util.Random;

import org.junit.Test;

public class App {
  private int n = 100000;
  @Test
  public void testFirst() {
    int[] arr = new int[n];
    long start = System.currentTimeMillis();
    for (int i = 0; i < n; i++) {
      arr[i] = readInt(1, n + 1);
      while (isExist(arr, i)) {
        arr[i] = readInt(1, n + 1);
      }
    }
    long end = System.currentTimeMillis();
    System.out.println("方法一消耗时长为:" + (end - start));
  }

  private boolean isExist(int[] arr, int index) {
    for (int i = 0; i < index; i++) {
      if (arr[i] == arr[index]) {
        return true;
      }
    }
    return false;
  }

  private int readInt(int i, int j) {
    Random random = new Random();
    int result = random.nextInt(j);
    while (result < i) {
      result = random.nextInt(j);
    }
    return result;
  }
}

       这里输出结果如下

方法一消耗时长为:38580

        即当n为100000的时候,计算结果需要38.580s。该算法通过readInt(int i, int j)方法获取一个大于等于i并且小于等于j的整数,通过isExist(int[] arr, int index)方法判断数组中在索引为index之前的序列里是否已经存在了索引为index对应的值。该算法求解的思路即为从0开始对数组arr赋值,并且在每次获取一个随机数之后判断数组之前的部分中是否已经存在了该值,若存在了该值则继续获取,直至数组之前的部分中不存在该值。这种算法将产生大量的重复计算,主要来源在于判断数组之前的部分中是否存在该值和对于新的数组元素的获取两个部分。为了解决第一个问题,即判断数组之前部分中是否存在该值,我们采用了第二种算法,具体代码如下:

import java.util.Random;

import org.junit.Test;

public class App {
  private int n = 100000;

  @Test
  public void testSecond() {
    int[] arr = new int[n];
    long start = System.currentTimeMillis();
    boolean[] used = new boolean[n];
    for (int i = 0; i < n; i++) {
      arr[i] = readInt(1, n + 1);
      while (used[arr[i] - 1]) {
        arr[i] = readInt(1, n + 1);
      }
      used[arr[i] - 1] = true;
    }
    long end = System.currentTimeMillis();
    System.out.println("方法二消耗时长为:" + (end - start));
  }

  private int readInt(int i, int j) {
    Random random = new Random();
    int result = random.nextInt(j);
    while (result < i) {
      result = random.nextInt(j);
    }
    return result;
  }
}

        计算结果如下:

方法二消耗时长为:148

        若将N改为1000000,计算结果为:1.648s,若将N改为10000000,计算结果为33.679s,可以看出,该算法相对于第一种算法有所改进,但是对于千万级数据量的处理消耗时长较长。第二种算法另外声明了一个数组used,该数组长度为N,这里将要求解的数据(长度为N的正整数的排列)与used数组的下标形成一种一一对应的关系,当要判断某个获取到的正整数是否已经存在时,只需要判断数组中对应下标的数据值是否为true,为true则表示已经存在。但是这里经过我们的分析也会发现,对于采用readInt(int i, int j)方法获取新数据时,若该数据非常靠后,那么获取的难度(循环的次数)将会大大增加,这里也会影响该算法的运行效率。为了避免这个问题,我们则可以采用第三种方法,该方法则使用了一个已知的事实,即结果数组中的数值我们是完全确定的,变化的只是该数值的顺序,因而,我们如果采用随机算法改变各个数值的位置,即可达到排列各个数值的目的。具体的算法如下:

import java.util.Random;

import org.junit.Test;

public class App {
  private int n = 10000000;

  @Test
  public void testThird() {
    int[] arr = new int[n];
    long start = System.currentTimeMillis();
    for (int i = 0; i < n; i++) {
      arr[i] = i + 1;
    }
    for (int i = 1; i < n; i++) {
      swapReferences(arr, i, readInt(0, i));
    }
    long end = System.currentTimeMillis();
    System.out.println("方法三消耗时长为:" + (end - start));
  }

  private void swapReferences(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

  private int readInt(int i, int j) {
    Random random = new Random();
    int result = random.nextInt(j);
    while (result < i) {
      result = random.nextInt(j);
    }
    return result;
  }
}

       运行结果如下:

方法三消耗时长为:2105

       该方法通过readInt(int i, int j)方法每次获取数组中索引为0到索引为i的随机索引,将并且将数组中索引为i的数据与获取到的索引对应的数据位置替换,这样就可以达到全排列的目的。

分享到:
评论

相关推荐

    删数问题算法程序(排列成一个新的正整数)

    本文探讨的问题是“删数问题算法程序(排列成一个新的正整数)”,该问题要求从一个给定的正整数中删除指定数量的数字,使剩余数字按原有顺序排列形成的新数尽可能小。 **问题描述:** - 给定一个长度为 \( n \)(\...

    问题描述:求从1~n的正整数中取出k(k<=n)个不重复整数的所有组合.pdf

    分析:求解k个数的不同组合,我们可以用一维数组a[0]~a[k-1]来保存其中的一个结果,因为组合元 素是不重复的,可以约定其递增排列,因为数组中的元素是递增排列的: 所以a[k-1]即组合中的最后一个数,只能为k~n 令i=...

    输出1到n的所有排列

    全排列是组合数学中的一个重要概念,...总结来说,本示例通过回溯法实现了全排列问题的求解,展示了如何利用编程来生成一个整数序列的所有可能排列,这对于理解和应用回溯法解决其他类似的组合问题具有重要的参考价值。

    Minimal m Sums 给定n 个整数组成的序列,现在要求将序列分割为m 段,每段子序列中的数在原序列中连续排列。如何分割才能使这m段子序列的和的最大值达到最小?

    - 给定一个包含 n 个整数的序列。 - 要求将这个序列分割为 m 个连续的子序列(每段子序列中的数在原序列中必须连续排列)。 - 目标是最小化这些子序列的和的最大值。 #### 输入输出格式 **输入**: - 第一行包含两...

    最优分解问题

    最优分解问题是一个经典的数学优化问题,它涉及到如何有效地将一个正整数n分解为若干个互不相同的自然数之和,以使得这些自然数的乘积最大化。这个问题在计算机科学和算法设计中有着广泛的应用,特别是在寻找高效...

    数列极差问题

    在这个问题中,初始有n个正整数排列成一个数列,每次操作擦去其中的两个数a和b,然后将它们的乘积加1的结果a×b+1写回数列,这个过程一直持续到数列只剩下一个数。最终的目标是找出所有可能的操作序列下,最大值max...

    ACM算法竞赛中第二类斯特林数O(n^2)求解代码

    给定一个正整数 n,表示要划分的物体的数量,以及一个正整数 k,表示要划分成的循环排列的数量,第二类斯特林数 S(n, k) 表示将这 n 个物体划分成 k 个非空循环排列的方法数。 第二类斯特林数满足以下递推关系: S...

    计算机中的第二类斯特林数“同一行求解”的C++代码实现

    给定一个正整数 n,表示要划分的物体的数量,以及一个正整数 k,表示要划分成的循环排列的数量,第二类斯特林数 S(n, k) 表示将这 n 个物体划分成 k 个非空循环排列的方法数。 第二类斯特林数满足以下递推关系: S...

    钱币组合方法问题

    1. **初始化数组:** 创建一个二维数组 `tmp`,其中 `tmp[i][j]` 表示用前 i 种钱币构成 j 元的组合方式的数量。 2. **处理第一种钱币:** 对于第一种钱币,如果目标金额可以被该种钱币整除,并且不超过拥有的数量,...

    组合数学中的第二类斯特林数“同一列”的C++代码实现

    给定一个正整数 n,表示要划分的物体的数量,以及一个正整数 k,表示要划分成的循环排列的数量,第二类斯特林数 S(n, k) 表示将这 n 个物体划分成 k 个非空循环排列的方法数。 第二类斯特林数满足以下递推关系: S...

    高考数学中解排列组合问题的17种策略.pdf

    16. 练习题的解题思路:通过具体的练习题来巩固排列组合的解题策略和方法,如分配学生干部培训指标的方案数问题,不定方程的正整数解问题等。 掌握上述策略和方法,考生不仅能够在高考数学中解决排列组合问题,而且...

    Python编程习题集chxx1

    1. **输入输出**:使用`input()`函数从键盘接收用户输入的两个正整数,然后通过除法和取模运算计算商和余数。输出结果可以使用`print()`函数。 2. **字符串操作**:获取用户输入的姓名,使用`len()`函数计算字符串...

    josephus排列问题

    接下来,第二个任务是找到一个正整数m,使得(n,m)Josephus排列的前k个数与预先指定的k个数完全相同。这通常更复杂,因为我们需要遍历不同的m值,直到找到满足条件的m。在`main`函数中,首先读取n、m以及指定的k个...

    《初等数论》第三章习题答案.rar

    1. 同余的概念及其基本性质:同余是整数之间的一种关系,如果两个整数除以某个正整数n得到相同的余数,我们就说它们对模n同余,表示为a ≡ b (mod n)。同余关系具有对称性、传递性和封闭性等基本性质,这些性质是...

    算法竞赛中的第一类斯特林数“同一行”的C++代码实现

    给定一个正整数n,表示要划分的物体的数量,以及一个正整数k,表示要划分成的循环排列的数量,第一类斯特林数 {n \atop k}(有时也写作c(n, k)或Stirling(n, k))表示将这n个物体划分成k个循环排列的方法数。...

    排列组合问题的转化方法[精选].doc

    (1)方程x + y + z = n的正整数解可以通过组合数C(n-1,2)得到。 (2)9名实习生分到6个班,每个班至少1人,可以使用隔板法,有C(5,3) = 10种分法。 4. **构造模型**: 构造模型可以帮助我们把抽象问题具体化。...

    C语言学习实例220例

    119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 129 飘带图案...

    排列组合练习题.doc

    表示1到n的所有正整数的乘积。 2. **组合**:从n个不同的元素中取出m个元素组成一组,不考虑元素之间的顺序,称为组合。组合数表示为C(n, m),公式为C(n, m) = n! / [m!(n-m)!],它代表的是从n个不同元素中无序选取...

    我探索全错位排列的过程

    为了解决上述问题,作者试图寻找一种通项公式,即当给定任意正整数n时,能够直接计算出对应的问题解的数量。在这个过程中,作者发现了一个有趣的递推关系: \[ a_n = (n - 1)(a_{n-1} + a_{n-2}), \quad n \geq 3; ...

Global site tag (gtag.js) - Google Analytics