正文
java穷举代码,穷举法java
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
Java 穷举问题
没有什么是绝对的,什么叫这个问题没人会解决的?
这个我正好有相应的解法,等一下贴出来:
//不用穷举法,用递归
public class InnerLoops {
public static void main(String[] args) {
String a = "0123456789";//可变
int rows = 3;//可变
char[][] c = new char[rows][];
for(int i=0; irows; i++)
c[i]=a.toCharArray();
inner(c,0,0);
}
public static final void inner(char[][] array,int currentRow,int currentColumn){
if(currentColumnarray[currentRow].length){
if(currentRow==array.length-1){
print(array);
}
if(hasNext(array,currentRow)){
inner(array,currentRow+1,0);
}
ring(array,currentRow);
inner(array,currentRow,currentColumn+1);
}
}
private static final boolean hasNext(char[][] array, int row) {
return array.lengthrow+1;
}
private static final void print(char[][] array) {
System.out.println(toString(array));
}
private static final String toString(char[][] array) {
String s = "";
for(int i=0; iarray.length; i++)
s+=(array[i][0]);
return s;
}
//使row行上的数往前推一位,溢出的0位补到最后一位
private static final void ring(char[][] array, int row) {
char t = array[row][0];
for(int i=1; iarray[row].length; i++)
array[row][i-1]=array[row][i];
array[row][array[row].length-1]=t;
}
}
相关问答
Q1: java实现二进制穷举
闲着没事，给你写了一个一个DFS算法，可以枚举（a1, a2… ak），剩下的太简单，你自己写着玩吧。。。
import java.util.ArrayList;
public class DFS {
public static void main(String[] args) {
DFS dfs=new DFS();
dfs.dfs(1);
}
int sum=0;
int index=5;
ArrayListIntegerlist=new ArrayListInteger();
public void dfs(int i)
{
if(iindex)
{
sum++;
System.out.println("this is the "+sum);
for(Integer integer:this.list)
{
System.out.print(integer+" ");
}
System.out.println();
return;
}
for(int j=0;j=1;j++)
{
list.add(j);
this.dfs(i+1);
list.remove(list.size()-1);
}
}
}
Q2: java 穷举出指定4个元素的一定长度的组合字符串
public class Main {
static StringBuilder sb;
public static void fn(String s,int len){
sb = new StringBuilder();
if(len s.length())
return;
for(int i = 1; i = len; i++){
emu(s,i);
}
}
public static void emu(String s,int len){
if(sb.length() = len) {
System.out.println(sb);
}
else {
for(int i = 0; i s.length(); i++){
sb.append(s.charAt(i));
emu(s,len);
sb.deleteCharAt(sb.length()-1);
}
}
}
public static void main(String[] args) {
fn("abcd",2);
}
}
Q3: java穷举搜索法，谁来写个!
算24点
穷举法
solution类
package test;
import java.util.Enumeration;
import java.util.Vector;
public class Solution {
static Vector numbers;
private boolean hasSolution;
private Vector theSolution;
private double theResult;
static final int TOTAL_POSITION = 13;
static final int NUM_POSITION[] = { 1, 4, 8, 11 };
static int numCombin[][] = new int[24][4];
static boolean hasNumCombin = false;
static final int OP_POSITION[] = { 2, 6, 10 };
static int opCombin[][] = new int[64][3];
static boolean hasOpCombin = false;
static Character whiteSpace = new Character(' ');
static Character openParen = new Character('(');
static Character closeParen = new Character(')');
static Character addition = new Character('+');
static Character subtract = new Character('-');
static Character multiply = new Character('*');
static Character division = new Character('/');
static final int PAREN_POSITION[] = { 0, 3, 5, 7, 9, 12 };
static final int PAREN_COMBIN[][] = { { 0, 0, 0, 0, 0, 0 },
{ 1, 0, 2, 0, 0, 0 }, { 1, 0, 0, 0, 2, 0 }, { 0, 1, 0, 0, 2, 0 },
{ 0, 1, 0, 0, 0, 2 }, { 0, 0, 0, 1, 0, 2 }, { 1, 0, 2, 1, 0, 2 } };
public Solution(int num0, int num1, int num2, int num3) {
theSolution = null;
numbers = new Vector(4);
numbers.addElement(new Integer(num0));
numbers.addElement(new Integer(num1));
numbers.addElement(new Integer(num2));
numbers.addElement(new Integer(num3));
searchSolution();
}
public Vector getSolution() {
return theSolution;
}
public boolean hasSolution() {
return hasSolution;
}
private static void numberCombination() {
Vector numbers = new Vector(4);
int count = 0;
if (hasNumCombin)
return;
for (int i = 0; i 4; i++)
numbers.addElement(new Integer(i));
for (int i = 0; i 4; i++) {
for (int j = 0; j 3; j++) {
for (int k = 0; k 2; k++) {
Vector tmpNumbers = (Vector) numbers.clone();
numCombin[count][0] = ((Integer) tmpNumbers.elementAt(i))
.intValue();
tmpNumbers.removeElementAt(i);
numCombin[count][1] = ((Integer) tmpNumbers.elementAt(j))
.intValue();
tmpNumbers.removeElementAt(j);
numCombin[count][2] = ((Integer) tmpNumbers.elementAt(k))
.intValue();
tmpNumbers.removeElementAt(k);
numCombin[count][3] = ((Integer) tmpNumbers.elementAt(0))
.intValue();
tmpNumbers.removeElementAt(0);
count++;
}
}
}
hasNumCombin = true;
}
private static void operatorCombination() {
int count = 0;
if (hasOpCombin)
return;
for (int i = 0; i 4; i++) {
for (int j = 0; j 4; j++) {
for (int k = 0; k 4; k++) {
opCombin[count][0] = i;
opCombin[count][1] = j;
opCombin[count][2] = k;
count++;
}
}
}
hasOpCombin = true;
}
private void searchSolution() {
Vector tmpExpression = new Vector(13);
int count = 0;
numberCombination();
operatorCombination();
for (int i = 0; i 13; i++)
tmpExpression.addElement(whiteSpace);
for (int num = 0; num 24; num++) {
for (int paren = 0; paren 7; paren++) {
for (int op = 0; op 64; op++) {
if (count++ % 500 == 0)
for (int i = 0; i 4; i++)
tmpExpression.setElementAt(numbers
.elementAt(numCombin[num][i]),
NUM_POSITION[i]);
for (int i = 0; i 6; i++)
switch (PAREN_COMBIN[paren][i]) {
case 1:
tmpExpression.setElementAt(openParen,
PAREN_POSITION[i]);
break;
case 2:
tmpExpression.setElementAt(closeParen,
PAREN_POSITION[i]);
break;
case 0:
tmpExpression.setElementAt(whiteSpace,
PAREN_POSITION[i]);
break;
}
for (int i = 0; i 3; i++)
switch (opCombin[op][i]) {
case 0:
tmpExpression
.setElementAt(addition, OP_POSITION[i]);
break;
case 1:
tmpExpression
.setElementAt(subtract, OP_POSITION[i]);
break;
case 2:
tmpExpression
.setElementAt(multiply, OP_POSITION[i]);
break;
case 3:
tmpExpression
.setElementAt(division, OP_POSITION[i]);
break;
}
try {
theResult = (new Expression(tmpExpression)).getValue();
} catch (IllegalExpressionException e) {
continue;
}
if (theResult == 24D) {
hasSolution = true;
theSolution = tmpExpression;
return;
}
}
}
}
hasSolution = false;
theSolution = null;
}
public static void printSolution(Vector theSolution) {
for (Enumeration e = theSolution.elements(); e.hasMoreElements();) {
System.out.print(e.nextElement());
}
}
public static void main(String[] args) {
Solution solution = new Solution(5, 7, 8, 9);
if (solution.hasSolution) {
printSolution(solution.getSolution());
}
}
}
IllegalExpressionException类
package test;
public class IllegalExpressionException extends Exception {
public IllegalExpressionException() {
}
public IllegalExpressionException(String msg) {
super(msg);
}
}
Expression类
package test;
import java.util.*;
public class Expression {
protected String inputExpression;
private Stack operatorStack;
private Stack postFixStack;
private final int EOL = 0;
private final int VALUE = 1;
private final int OPAREN = 2;
private final int CPAREN = 3;
private final int MULT = 4;
private final int DIV = 5;
private final int PLUS = 6;
private final int MINUS = 7;
private final int INPUT_PRECEDENCE[] = { 0, 0, 100, 0, 3, 3, 1, 1 };
private final int STACK_PRECEDENCE[] = { -1, 0, 0, 99, 4, 4, 2, 2 };
private double currentValue;
private double theResult;
private int lastToken;
public Expression() {
inputExpression = null;
operatorStack = new Stack();
postFixStack = new Stack();
operatorStack.push(new Integer(0));
}
public Expression(String inString) {
inputExpression = inString.trim();
operatorStack = new Stack();
postFixStack = new Stack();
operatorStack.push(new Integer(0));
}
public Expression(Vector inVector) {
StringBuffer tmpString = new StringBuffer();
for (Enumeration e = inVector.elements(); e.hasMoreElements(); tmpString
.append(e.nextElement()))
;
inputExpression = tmpString.toString().trim();
operatorStack = new Stack();
postFixStack = new Stack();
operatorStack.push(new Integer(0));
}
public void setExpression(String inString) {
inputExpression = inString.trim();
}
public String getExpression() {
return removeSpace(inputExpression);
}
public double getValue() throws IllegalExpressionException {
StringTokenizer parser = new StringTokenizer(inputExpression,
"+-*/() ", true);
do
if (!parser.hasMoreTokens()) {
lastToken = 0;
processToken();
} else {
String token = parser.nextToken();
char firstChar = token.charAt(0);
if (!Character.isWhitespace(firstChar)) {
if (token.length() == 1 isOperator(firstChar)) {
switch (firstChar) {
case '+':
lastToken = PLUS;
break;
case '-':
lastToken = MINUS;
break;
case '*':
lastToken = MULT;
break;
case '/':
lastToken = DIV;
break;
case '(':
if (lastToken != VALUE)
lastToken = OPAREN;
else
throw new IllegalExpressionException(
"Missing operator");
break;
case ')':
lastToken = CPAREN;
break;
}
} else {
try {
currentValue = Double.valueOf(token).doubleValue();
} catch (NumberFormatException e) {
throw new IllegalExpressionException(
"Unknown symbol");
}
if (lastToken != 1 lastToken != 3)
lastToken = 1;
else
throw new IllegalExpressionException(
"missing operator");
}
processToken();
}
}
while (lastToken != EOL);
if (postFixStack.empty())
throw new IllegalExpressionException("Missing operand");
theResult = ((Double) postFixStack.pop()).doubleValue();
if (!postFixStack.empty())
throw new IllegalExpressionException("Missing operator");
else
return theResult;
}
private String removeSpace(String inputString) {
StringBuffer s = new StringBuffer();
for (int i = 0; i inputString.length(); i++) {
char c;
if ((c = inputString.charAt(i)) != ' ')
s.append(inputString.charAt(i));
}
return s.toString();
}
private void processToken() throws IllegalExpressionException {
switch (lastToken) {
case VALUE:
postFixStack.push(new Double(currentValue));
return;
case CPAREN:
int topOperator;
while ((topOperator = ((Integer) operatorStack.peek()).intValue()) != OPAREN
topOperator != EOL)
applyOperation(topOperator);
if (topOperator == OPAREN)
operatorStack.pop();
else
throw new IllegalExpressionException("Missing open parenthesis");
break;
default:
while (INPUT_PRECEDENCE[lastToken] = STACK_PRECEDENCE[topOperator = ((Integer) operatorStack
.peek()).intValue()])
applyOperation(topOperator);
if (lastToken != EOL)
operatorStack.push(new Integer(lastToken));
break;
}
}
private void applyOperation(int topOperator)
throws IllegalExpressionException {
if (topOperator == OPAREN)
throw new IllegalExpressionException("Unbalanced parenthesis");
double rightOperand = getPostStackTop();
double leftOperand = getPostStackTop();
if (topOperator == PLUS)
postFixStack.push(new Double(leftOperand + rightOperand));
else if (topOperator == MINUS)
postFixStack.push(new Double(leftOperand - rightOperand));
else if (topOperator == MULT)
postFixStack.push(new Double(leftOperand * rightOperand));
else if (topOperator == DIV)
if (rightOperand != (double) 0)
postFixStack.push(new Double(leftOperand / rightOperand));
else
throw new IllegalExpressionException("Division by zero");
operatorStack.pop();
}
private double getPostStackTop() throws IllegalExpressionException {
if (postFixStack.empty())
throw new IllegalExpressionException("Missing operand");
else
return ((Double) postFixStack.pop()).doubleValue();
}
private boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/' || c == '('
|| c == ')';
}
}
Q4: java循环穷举
代码如下：
public class Min_Number {
public static void main(String[] args) {
int num = 5;
int resa, resb, resc, resd, rese;
ListInteger list = new ArrayList();
for (int a = 1; a = num; a++) {
resa = a * 10000;
for (int b = 1; b = num; b++) {
if (b == a) {
continue;
}
resb = resa + b * 1000;
for (int c = 1; c = num; c++) {
if (c == a || c == b) {
continue;
}
resc = resb + c * 100;
for (int d = 1; d = num; d++) {
if (d == a || d == b || d == c) {
continue;
}
resd = resc + d * 10;
for (int e = 1; e = num; e++) {
if (e == a || e == b || e == c || e == d) {
continue;
}
rese = resd + e * 1;
if (rese % 7 == 0) {
list.add(rese);
}
}
}
}
}
}
Object[] objects = list.toArray();
Arrays.sort(objects);
System.out.println("由1,2,3,4,5五个数字组成的能被7整除的最小五位数是：" + (int) objects[0]);
}
}
运行效果：
Q5: C# 或java 穷举算法、
这是一个经典的全排列算法问题 我把算法写在下边 是C#的
using System;
using System.Collections.Generic;
using System.Windows.Forms;
namespace Pailie
{
static class Program
{
/// summary
/// 应用程序的主入口点。
/// /summary
[STAThread]
static void Main()
{
string s = "abcd";//用于计算全排列的输入字符串
char[] add = s.ToCharArray();
pai(ref add, 0, s.Length);
}
//递归算法
// str:输入的字符串toChar结果
//m ：重排列的起始位置。全排列起始位置为0
//n: 排列长度 全排列起始位置为字符串长度
private static void pai(ref char[] str, int m, int n)
{
if (m n)
{
for (int i = 0; i = m; i++)
{
pai(ref str, m + 1, n);
chang(ref str, m);
}
}
else
{
Console.WriteLine(str);
}
}
//移位
private static void chang(ref char[] str, int m)
{
char temp = str[0];
for (int i = 0; i m; i++)
{
str[i] = str[i + 1];
}
str[m] = temp;
}
}
}
写个算法不容易。多少加点分吧
