子字符串组合 java_abc三字符实现排列组合-JAVA版

淩亂°似流年 2022-10-22 11:57 147阅读 0赞

1.概述

在高中的时候经常会遇到一些排列组合的问题，那个时候基本上都是基于公式计算的。其实理论上是可以枚举出来的，而计算机最擅长的事情就是枚举，本文主要讨论a,b,c三个字符的各种排列组合问题，当字符增加的时候，思路是相同的。

2.可重复排列

可重复排列就是给定，a,b,c三个字符，组成长度为3的字符串，其中a,b,c可以使用多次。这个时候可以使用递归思想：第一个字符从a,b,c中选择一个，之后的问题转化为：a,b,c三个字符组成长度为2的字符串。控制好递归退出的条件，即可。

public class Permutation \{

public static void main(String\[\] args) \{

char\[\] chs = \{'a', 'b', 'c'\};

per(new char\[3\], chs, 3 - 1);

\}

public static void per(char\[\] buf, char\[\] chs, int len) \{

if (len == -1) \{

for (int i = buf.length - 1; i >= 0; --i) \{

System.out.print(buf\[i\]);

\}

System.out.println();

return;

\}

for (int i = 0; i < chs.length; i++) \{

buf\[len\] = chs\[i\];

per(buf, chs, len - 1);

\}

\}

\}

3.全排列

全排列的意思，就是只能用a,b,c三个元素，做排列，每个用且只能用一次。

也可以利用递归，第一个字符串一共有n种选择，剩下的变成一个n-1规模的递归问题。而第一个字符的n种选择，都是字符串里面的。因此可以使用第一个字符与1-n的位置上进行交换，得到n种情况，然后递归处理n-1的规模，只是处理完之后需要在换回来，变成原来字符的样子。

public class Permutations \{

public static void main(String\[\] args) \{

char\[\] arrs = \{'a','b','c'\};

List> results = new Permutations().permute(arrs);

for (List tempList : results)\{

System.out.println(String.join(",",

tempList.stream().map(s->String.valueOf(s)).collect(Collectors.toList())));

\}

\}

public List> permute(char\[\] nums) \{

List> lists = new LinkedList<>();

tempPermute(nums, 0, lists);

return lists;

\}

public void tempPermute(char\[\] nums, int start, List> lists)\{

int len = nums.length;

if(start == len-1)\{

List l = new LinkedList<>();

for(char num : nums)\{

l.add(num);

\}

lists.add(l);

return;

\}

for(int i=start; i

char temp = nums\[start\];

nums\[start\] = nums\[i\];

nums\[i\] = temp;

tempPermute(nums, start+1, lists);

temp = nums\[start\];

nums\[start\] = nums\[i\];

nums\[i\] = temp;

\}

\}

\}

在1中使用打印的方式，这里使用返回值的方式，因为有些场景我们希望得到值并且返回。

4.组合

求所有组合也就是abc各个位是否选取的问题，第一位2中可能，第二位2种。。。所以一共有2n种。用0表示不取，1表示选取，这样可以用110这样的形式表示ab。abc一共的表示形式从0到23-1。然后按位与运算，如果结果为1就输出当前位，结果0不输出。

public class Comb \{

public static void main(String\[\] args) \{

char\[\] chs = \{'a','b','c'\};

comb(chs);

\}

public static void comb(char\[\] chs) \{

int len = chs.length;

int nbits = 1 << len;

for (int i = 0; i < nbits; ++i) \{

int t;

for (int j = 0; j < len; j++) \{

t = 1 << j;

if ((t & i) != 0) \{ // 与运算，同为1时才会输出

System.out.print(chs\[j\]);

\}

\}

System.out.println();

\}

\}

\}

发表评论取消回复

表情：

评论列表（有 0 条评论，147人围观）

还没有评论，来说两句吧...

相关阅读

相关 java实现排列组合算法

我这里只写了组合的算法。假设现有 M=4 个数据 a，b，c，d。从中随机抽取n个数，n为1—4个数据进行组合。那么数学中的计算组合方式为C(4,1) + C(4,2) +

以你之姓@/ 2024年03月22日 14:45/ 0 赞/ 59 阅读

相关 java实现排列组合

数学问题 - java实现排列组合 -------------------- 今天遇到一个组合问题，整理学习相关数学算法问题，并做记录。如果和我一样已经忘记数学集合

朴灿烈づ我的快乐病毒、/ 2022年12月21日 14:58/ 0 赞/ 115 阅读

相关子字符串组合 java_abc三字符实现排列组合-JAVA版

1.概述在高中的时候经常会遇到一些排列组合的问题，那个时候基本上都是基于公式计算的。其实理论上是可以枚举出来的，而计算机最擅长的事情就是枚举，本文主要讨论a,b,c三个字符

淩亂°似流年/ 2022年10月22日 11:57/ 0 赞/ 148 阅读

相关字符串排列和组合的JAVA实现

字符串的组合：给一个字符串，比如ABC，把所有的组合，即：A, B, C, AB, AC, BC, ABC, 都找出来。解题思路：假设我们想在长度为n的字符串中求

男娘i/ 2022年09月26日 02:21/ 0 赞/ 162 阅读

相关 Java 排列组合字符串

例如输入“abc”，打印所有可能出现的组合情况,并且消除重复值。所谓排列组合如下：排列组合,字符串:abc bca acb abc

r囧r小猫/ 2022年08月23日 00:45/ 0 赞/ 172 阅读

相关字符串排列组合

网上有好多字符串排列组合的文章，自己看了，学习了，把代码留下，以备以后用。自己也写了个八皇后的代码，也留着以后复习方便。 include<iostream>

妖狐艹你老母/ 2022年08月07日 12:46/ 0 赞/ 182 阅读

相关字符串的排列/组合

排列字符串“abc”的全排列： abc acb bac bca cba cab 求整个字符串的排列，可以分为两步：第一步，求所有可能出现在第

曾经终败给现在/ 2022年08月01日 06:21/ 0 赞/ 162 阅读

相关字符串的排列与组合

字符串的全排列题目：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,

- 日理万妓/ 2022年05月21日 09:18/ 0 赞/ 180 阅读

相关 Java实现排列组合

基本概念阶乘在介绍排列组合前首先要介绍阶乘，因为很多排列组合的运算都是要用上阶乘。阶乘的定义如下：`一个正整数的阶乘（factorial）是所有小于及等于该数的

迷南。/ 2022年05月14日 05:46/ 0 赞/ 332 阅读

相关组合数学 (三): 排列组合的数学逻辑

排列组合的数学逻辑前言排列圆排列项链排列组合 n 个相同的小球放到 m 个相同的盒子里

怼烎@/ 2022年02月14日 01:18/ 0 赞/ 604 阅读