精华内容
参与话题
问答
  • permutation()的使用

    万次阅读 2018-09-07 21:18:30
    numpy.random.permutation(x) 随机排列一个序列,或者数组。 如果x是多维数组,则沿其第一个坐标轴的索引随机排列数组。 参数: x : 整数或者数组 如果x是整数,则随机排列np.arange(x)。若果x是数组,对其复制...

    语法格式:
    numpy.random.permutation(x)
    随机排列一个序列,或者数组。

    如果x是多维数组,则沿其第一个坐标轴的索引随机排列数组。

    参数:
    x : 整数或者数组
    如果x是整数,则随机排列np.arange(x)。若果x是数组,对其复制之后再搅乱其元素。

    返回:
    out : 排列的序列或数组

    np.random.permutation(10)
    输出:
    array([1, 7, 4, 3, 0, 9, 2, 5, 8, 6])
    np.random.permutation([1, 4, 9, 12, 15])
    输出:
    array([15,  1,  9,  4, 12])
    arr = np.arange(9).reshape((3, 3))
    np.random.permutation(arr)
    输出:
    array([[6, 7, 8],
           [0, 1, 2],
           [3, 4, 5]])
    展开全文
  • Permutation

    2019-01-19 22:36:23
    template <typename T> void Permutations(T* list, const int k, const int n) {  if (k == n)  {  for (int i = 0; i <= n; ++i)  {  std::cout <&... ...

    template <typename T>
    void Permutations(T* list, const int k, const int n)
    {
        if (k == n)
        {
            for (int i = 0; i <= n; ++i)
            {
                std::cout << list[i];
            }
            std::cout << std::endl;
        }
        else
        {
            for (int i = k; i <= n; ++i)
            {
                std::swap(list[k], list[i]);
                Permutations(list, k + 1, n);
                std::swap(list[k], list[i]);
            }
        }
    }

    展开全文
  • permutation

    2020-07-26 17:22:44
    Problem Description 一开始有n个数,他们按1...n的顺序排列,要求交换最多m对数字(同一个数字可以参与多次交换),使得逆序对数目最大。 对于一个序列A,如果存在正整数i, j使得1≤i<j≤n而且A[i] >...

    Problem Description

    一开始有 n个数,他们按 1...n的顺序排列,要求交换最多 m对数字(同一个数字可以参与多次交换),使得逆序对数目最大。

    对于一个序列 A,如果存在正整数 i, j使得1≤i<j≤n 而且 A[i] > A[j],则<A[i],A[j]> 这个有序对称为 A 的一个逆序对。

    Input

    第一行一个正整数 test (1≤test≤100000) 表示数据组数。

    对于每组数据,一行两个整数 n,m (1≤n≤1000000,0≤m≤1000000) 表示数字个数和最多可以交换的数字对数。

    Output

    对于每组数据,一行一个整数表示答案。

    Sample Input

    6
    1 1
    2 0
    2 1
    3 1
    4 1
    4 2

    Sample Output

    0
    0
    1
    3
    5
    6
    #include <iostream>
    #include<math.h>
    #include <vector>
    #include <algorithm>
    #include <queue>
    #include <set>
    using namespace std;
    
    int main() {
    	int test;
    	cin >> test;
    	while (test--) {
    		long long int a;
    		long long int b;
    		scanf("%d", &a);
    		scanf("%d", &b);
    		if (2 * b <= a) {
    			printf("%lld\n", (2 * a - 2 * b - 1) * b);
    		}
    		else {
    			long long int c = a / 2;
    			printf("%lld\n", (2 * a - 2 * c - 1) * c);
    		}
    	}
    	return 0;
    }

     

    展开全文
  • permutation 系列

    千次阅读 2014-05-02 13:55:59
    关于permutation的讲解,请参见http://blog.csdn.net/xuqingict/article/details/24840183 下列题目的讲解均是基于上面的...Next Permutation  Total Accepted: 8066 Total Submissions: 32493My Submissions

    关于permutation的讲解,请参见http://blog.csdn.net/xuqingict/article/details/24840183

    [updated 2014.7.30]

    所有的Permutation无论是否有重复元素,直接使用下面的代码即可,

    bool helper(vector<int> &num)
    {
        if(num.empty()) return false;
        typedef vector<int>::iterator iter;
        iter first=num.begin(), last=num.end();
        --last;
        if(first==last) return false;
        while(last != first && !(*(last-1) < *last))--last;  //此处直接使用!< 即可。。。
        if(last==first) return false;
        iter left=last-1,right=last;
        last=num.end();
        --last;
        while(!(*left < *last))--last;   //同上!!!
        iter_swap(left,last);
        reverse(right,num.end());
        return true;
    }
    public:
        vector<vector<int> > permuteUnique(vector<int> &num) {
            if(num.empty()) return vector<vector<int> >();
            vector<vector<int> > ret;
            sort(num.begin(), num.end());
            do
            {
                ret.push_back(num);
            }while(helper(num));
            return ret;
        }


    下列题目的讲解均是基于上面的文章:


    题1: 

    Next Permutation

     Total Accepted: 8066 Total Submissions: 32493My Submissions

    Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

    If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

    The replacement must be in-place, do not allocate extra memory.

    Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
    1,2,3 → 1,3,2
    3,2,1 → 1,2,3
    1,1,5 → 1,5,1


    给定一个permutation,直接求出下一个:

    class Solution {
    public:
        void nextPermutation(vector<int> &num) {
            typedef vector<int>::iterator iter;
            iter beg = num.begin(), end = num.end();
            if( beg == end || beg + 1 == end)return;
            
            iter right = end;
            --right;
            for(;;)
            {
                iter left = right;
                --left;
                
                if(*left < *right)
                {
                    iter k = end;
                    while(!(*left < *--k)){}
                    iter_swap(left, k);
                    reverse(right,end);
                    return;
                }
                --right;
                if(right == beg)
                {
                    reverse(beg, end);
                    return;
                }
            }
        }
    };

    题2:

    Permutations

     Total Accepted: 12960 Total Submissions: 42049My Submissions

    Given a collection of numbers, return all possible permutations.

    For example,
    [1,2,3] have the following permutations:
    [1,2,3][1,3,2][2,1,3][2,3,1][3,1,2], and [3,2,1].

    返回 所有的permutation


    class Solution {
    private:
    typedef vector<int>::iterator iter;
    bool helper(iter first, iter last)
    {
        if(first == last) return false;
    
        if(first + 1 == last) return false;
    
        iter j = last;
        --j;
    
        while(1)
        {
            iter i = j;
            --i;
            //find a[i] < a[j] and they are adjacent
            if(*i < *j)
            {
                iter k = last;
                while(!(*i < *--k)){}
                std::swap(*i,*k);
                std::reverse(j,last);
                return true;
            }
            --j;
            //no such a[i] < a[i+1] pair found
            if( j == first)
            {
                //restore the first of the permutation
                std::reverse(first, last);
                return false;
            }
        }
        
    }
    public:
        vector<vector<int> > permute(vector<int> &num) {
            vector<vector<int> > ret;
            if(num.empty())return ret;
    
            iter beg = num.begin(), end = num.end();
            
            if(beg + 1 == end)
            {
                ret.push_back(num);
                return ret;
            }
            sort(beg,end); //首先必须sort!!!!
            
            do{
                ret.push_back(num);
            }while(helper(beg, end));
            
            return ret;
        }
    };



    题3:

    Given a collection of numbers that might contain duplicates, return all possible unique permutations.

    For example,
    [1,1,2] have the following unique permutations:
    [1,1,2][1,2,1], and [2,1,1].

    有重复元素的permutation,使用set结构来存储结果即可:

    class Solution {
    private:
    typedef vector<int>::iterator iter;
    bool permutation(iter beg, iter end)
    {
        if(beg == end || beg + 1 == end)
        {
            return false;
        }
        iter right = end;
        --right;
        while(1)
        {
            iter left = right;
            --left;
            if(*left < *right)
            {
                iter k = end;
                while(!(*left < *--k)){}
                iter_swap(left,k);
                reverse(right,end);
                return true;
            }
            --right;
            if(right == beg)
            {
                reverse(beg,end);
                return false;
            }
        }
    }
    
    public:
        vector<vector<int> > permuteUnique(vector<int> &num) {
            set<vector<int> > unique;
            sort(num.begin(), num.end());
            
            do
            {
                if(unique.count(num) == 0 )
                    unique.insert(num);
            }while(permutation(num.begin(),num.end()));
            
            vector<vector<int> > ret(unique.begin(), unique.end());
            
            /*for(set<vector<int> >::iterator it = unique.begin();
            it != unique.end() ; ++it)
            {
                ret.push_back(*it);
            }*/
            
            return ret;
        }
    };

    题4 : 给出第k-th个permutation:

    Permutation Sequence

     Total Accepted: 6704 Total Submissions: 31386My Submissions

    The set [1,2,3,…,n] contains a total of n! unique permutations.

    By listing and labeling all of the permutations in order,
    We get the following sequence (ie, for n = 3):

    1. "123"
    2. "132"
    3. "213"
    4. "231"
    5. "312"
    6. "321"

    Given n and k, return the kth permutation sequence.

    Note: Given n will be between 1 and 9 inclusive.


    解题思路:

    首先,假设  n = 3, k = 4 , 我们可以得到上述的编码,可以发现,前 (n-1)!个元素是以  1  开头的,,第二组 (n-1)!的元素是以2开头的,那么我们就可以有

     k = 4 = 2*2! + 0* 1! + 0*0!,那么该串中的字符应该是第2个,第0个,以及第0个字符,这里请注意,每一步的原始的元素集合是在减少1 的,比如;

    第2个意味着 “123”的第2个,为‘3’, 那么此时的串变为 “12”

    第0个意味着 “12”的第0个, 为 ‘1’,那么此时的串变为 “2”

    第0个意味着 “2”的第0个,为 ‘2’, 那么此时串为空,结束,那么结果即为 “312”。

    但是我们发现现在求的 “312”实际上是第5个(因为结果是从1开始的),因此只需要在计算之前将 k减一即可。也就是说在k之前一共有  k-1 个permutation,因此代码为:


    class Solution {
    public:
        string getPermutation(int n, int k) 
        {
            string str;
            for(int i = 1 ; i <= n ; ++i)
                str += ('0' + i);
                
            string ret;
            
            int base = 1;
            for(int i = n-1 ; i >= 1 ; --i)
            {
                base *= i;
            }
            
            
            --k;
            int i = n-1;
            while(i > 0 && k > 0) // iterate (n-1) times
            {
                int pos = k/base;
                k = k % base;
                ret += str[pos];
                str.erase(pos,1);
                base /= i;
                --i;
            }
            //[updated] 可以直接写成if(!str.empty()) ret+=str;
            while(!str.empty())
            {
                ret += str[0];
                str.erase(0,1);
                --i;
            }
            return ret;
                
        }
    };

    上述permutation的题目,比较函数默认为less,如果为greater是同样的道理。


    展开全文
  • 排列组合(permutation)系列解题报告

    万次阅读 2014-10-18 18:46:15
    本文讲解4道关于permutation的题目。 1. Permutation:输出permutation——基础递归 2. Permutation Sequence: 输出第k个permutation——推理 3. Next Permutation:给定一个permutation中的序列,求字典序它的下一...
  • 全排列函数permutation

    千次阅读 2019-03-29 15:14:04
    这个函数有两个一个是next_permutation()另一个是prev_permutation(),第一个是求原排列的下一个排列,第二个是求原排列的上一个排列,当上一个排列或下一个排列不存在时,返回false。 假如我们有长度为3的排列...
  • Python之permutation()的使用

    千次阅读 2019-11-06 10:14:52
    numpy.random.permutation(x) 随机排列一个序列,或者数组。 如果x是多维数组,则沿其第一个坐标轴的索引随机排列数组。 参数: x : 整数或者数组 如果x是整数,则随机排列np.arange(x)。若果x是数组,对其复制之后...
  • C++中全排列函数next_permutation 用法

    万次阅读 多人点赞 2017-03-29 14:38:25
    全排列参考了两位的博客 感谢! ... 早就听说了了next_permutation 产生全排列的强大,一直到昨晚遇到一个对字符串产生全排列的问题才知道这个函数的强大,我们队是按照
  • next_permutation用法

    千次阅读 2018-09-11 21:27:00
    当需要对一个序列中的元素进行全排列,可以使用该函数。 bool next_permutation(BidirectionlIterator first,BidirectionalIterator last); 包含于头文件 int a[]={1,2,3,4,5}; //产生所有下一组合,时间复杂度...
  • C++ next_permutation 用法

    2019-08-11 17:24:25
    组合数学中经常用到排列,这里介绍一个计算序列全排列的函数:next_permutation(start,end),和prev_permutation(start,end)。这两个函数作用是一样的,区别就在于前者求的是当前排列的下一个排列,后一个求的是...
  • next_permutation函数用法举例

    千次阅读 多人点赞 2018-04-28 20:40:00
    按照STL文档的描述,next_permutation函数将按字母表顺序生成给定序列的下一个较大的排列,直到整个序列为降序为止。prev_permutation函数与...使用方法next_permutation(数组头地址,数组尾地址);若下一个排列存...
  • next_permutation用法 与 字典序

    千次阅读 2015-09-02 15:30:12
    next_permutation用法在标准库算法中,next_permutation应用在数列操作上比较广泛.这个函数可以计算一组数据的全排列.下面是简单的剖析.首先查看stl中相关信息.函数原型: template  bool next_permutation(  ...
  • 给大家推荐个靠谱的公众号程序员探索之路,大家一起加油 next函数默认的是从小到大的顺序,pre函数默认的是从大到小的顺序; {3,1,2}用next得到的结果是{3,...【STL】next_permutation的原理和使用  1、碰到ne...
  • next_permutation函数将按字母表顺序生成给定序列的下一个较大的排列,直到整个序列为降序为止。prev_permutation函数与之相反,是生成给定序列的上一个较小的排列。二者原理相同,仅遍例顺序相反 百度文库: 这...
  • next_permutation函数: 组合数学中经常用到排列,这里介绍一个计算序列全排列的函数:next_permutation(start,end),和prev_permutation(start,end)。这两个函数作用是一样的,区别就在于前者求的是当前排列的...
  • 文章目录一、本文目标二、next_permutation算法和思想三、next_permutation具体实现四、prev_permutation算法和思想五、prev_permutation具体实现六、总结和分析 一、本文目标 在【其一 排列组合和子集生成】这篇...
  • next_permutation的思想和用法

    千次阅读 2016-03-15 21:44:53
    #include #include using namespace std; int main(){ int a[4]={1,2,3,4}; do{ cout[0][1][2][3]; } while(next_permutation(a,a+4)); system("pause"); } 该段代码意思为求1,2,
  • 用法总结】C++ STL中 next_permutation函数的用法

    千次阅读 多人点赞 2018-03-25 10:06:32
    参考链接:点击打开链接概述与分析 STL提供了两个用来计算排列组合关系的算法,分别是next_permutation和prev_permutation。首先我们必须了解什么是“下一个”排列组合,什么是“前一个”排列组合。考虑三个字符所...
  • 全排列函数next_permutation与prev_permutation
  • next_permutation的正确使用方法

    千次阅读 2019-03-23 18:52:22
    1. 使用全排列函数前要先对数组排序,推荐使用sort函数! 2. 使用do while结构的循环 #include <iostream> #include <algorithm> using namespace std; int main() { int a[4]={1,5,4,3},i; sort(a....
  • 标准库中next_permutation函数:找当前序列中元素排列的下一个排列,按照字典顺序进行排列。比如说数组排列"123",那么它的下一个排列为"132",并且返回true。如果当前序列没有下一个排列,我们...
  • #include #include #include #define max_n 1010 using namespace std; int a[max_n]; int main() { int n; while(scanf("%d",&n)!=EOF) { for(int i=0;i;i++) scanf("%d",&a[i]);... do
  • C++STL中全排列函数next_permutation使用

    万次阅读 多人点赞 2015-04-27 12:35:02
    next_permutation函数  组合数学中经常用到排列,这里介绍一个计算序列全排列的函数:next_permutation(start,end),和prev_permutation(start,end)。这两个函数作用是一样的,区别就在于前者求的是当前排列...
  • 全排列与next_permutation

    千次阅读 2016-07-27 16:01:23
    全排列是面试笔试过程中经常遇到的一个问题。对于练习过的同学来说,这个问题其实 不算一个难题,但是对于没有练习过的同学,或者说只是知道大致思路的同学来... STL中的next_permutation全排列的递归实现递归方法的全
  • 全排列 next_permutation使用

    千次阅读 2019-06-01 20:48:28
    题目描述: 给定一个由不同的小写字母组成的字符串,输出这个字符串的所有全排列。 我们假设对于小写字母有'a' < 'b' < ...... 'y' < 'z',而且给定的字符串中的字母已经按照从小到大的顺序排列。...
  • next-permutation用于全排列,比dfs不知道高到哪里去了~(+1s) 1.基本框架int a[]; do {}while(next_permutation(a+1,a+n+1));2.代码#include #include #include using namespace std; int main() { int a
  • next_permutation string s="ABC"; next_permutation(s,s+3) 排列就是一次对对象序列或值序列的重新排列。例如,“ABC”中字符可能的排列是: “ABC”, “ACB”, “BAC”, “BCA”, “CAB”, “CBA” next_...
  • next_permutation一些介绍

    2018-09-07 20:27:19
    (1)基本用法(参照王小二的哈哈): #include&lt;bits/stdc++.h&gt; using namespace std; const int maxn = 1e3; int a[maxn]; int main() { int n; while(cin&gt;&gt;n) { for(int i=0;i&...
  • /*对于一组给定的序列你可以从小到大或者从大到小排列,stl中有两个库函数很好用:next_permutation和prev_permutation 但是这里要注意 要在do while循环中写才会将所有你想排列都写出来,在for或者while循环中会将...
  • 在标准库算法中,next_permutation应用在数列操作上比较广泛.这个函数可以计算一组数据的全排列.但是怎么用,原理如何,我做了简单的剖析. 首先查看stl中相关信息. 函数原型: [cpp] view plaincopy ...

空空如也

1 2 3 4 5 ... 20
收藏数 50,685
精华内容 20,274
关键字:

permutation