全排列(求所有情况的个数)--10--全排列--蓝桥杯凑算式和leetcode46全排列

题目描述

 
这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。 
比如： 
6+8/3+952/714 就是一种解法，5+3/1+972/486 是另一种解法。 
这个算式一共有多少种解法？ 

输出

输出一个整数表示答案 

 

分析

　　这是一道典型的全排列算法的应用。将1~9组成的序列全排列出来，再来挑选符合算式结构的情况。

　　全排列的算法思想理解1：将原序列中的每个位置的数与原序列的该位置后面的每个数进行交换。

#include <iostream>
#include <vector>
#include <stdio.h>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int n = 1*2*3*4*5*6*7*8*9+5;
vector<double>num[n];
int sum = 0;
void perm(vector<double>my,int l,int r){
    if(l > r){
        num[sum] = my;
        for(int i = 0;i < 9;i++)
              cout << my[i] <<" ";
        cout << endl;
        sum++;
    }
    else{
        for(int i = l;i <= r;i++){
            swap(my[l],my[i]);
            perm(my,l + 1,r);
            swap(my[l],my[i]);
        }
    }
}
int main(){
    vector<double>my;
    double a,b,c,D,E;
    for(int i = 0;i < 9;i++){
        my.push_back(i+1);
    }
    perm(my,0,8);
    cout << sum <<endl;
    int zz = sum;
    for(int i = 0;i < zz;i++){
         a = num[i][0];
         b = num[i][1];
         c = num[i][2];
         D = num[i][3]*100.0+num[i][4]*10.0+num[i][5];
         E = num[i][6]*100.0+num[i][7]*10.0+num[i][8];

        if(a+(b/c)+(D/E) != 10.0)
            sum--;
    }
    cout << sum <<endl;
    return 0;
}

                

全排列

　　给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:
　　输入: [1,2,3]
　　输出:
　　　　[
  　　　　[1,2,3],
  　　　　[1,3,2],
  　　　　[2,1,3],
  　　　　[2,3,1],
  　　　　[3,1,2],
  　　　　[3,2,1]
　　　　]

Java代码演示

class Solution {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    public void swap(int[] num,int i,int j){
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
    public void perm(int[] nums,int left,int right){
        if(left > right){
            List<Integer> list = new ArrayList<Integer>();
            for(int i = 0;i < nums.length;i++){
                list.add(nums[i]);
            }
            res.add(list);
        }

        for(int i = left;i <= right;i++){
            swap(nums,left,i);
            perm(nums,left+1,right);
            swap(nums,left,i);
        }
    }
    public List<List<Integer>> permute(int[] nums) {
        if(nums.length == 0){
            List<Integer> list = new ArrayList<Integer>();
            res.add(list);
            return res;
        }
        perm(nums,0,nums.length - 1);
        return res;
    }
}