我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
这个答案怎么样……这将打印所有长度为3的组合…它可以推广到任何长度… 工作代码…
#include<iostream>
#include<string>
using namespace std;
void combination(string a,string dest){
int l = dest.length();
if(a.empty() && l == 3 ){
cout<<dest<<endl;}
else{
if(!a.empty() && dest.length() < 3 ){
combination(a.substr(1,a.length()),dest+a[0]);}
if(!a.empty() && dest.length() <= 3 ){
combination(a.substr(1,a.length()),dest);}
}
}
int main(){
string demo("abcd");
combination(demo,"");
return 0;
}
其他回答
我想提出我的解决方案。在next中没有递归调用,也没有嵌套循环。 代码的核心是next()方法。
public class Combinations {
final int pos[];
final List<Object> set;
public Combinations(List<?> l, int k) {
pos = new int[k];
set=new ArrayList<Object>(l);
reset();
}
public void reset() {
for (int i=0; i < pos.length; ++i) pos[i]=i;
}
public boolean next() {
int i = pos.length-1;
for (int maxpos = set.size()-1; pos[i] >= maxpos; --maxpos) {
if (i==0) return false;
--i;
}
++pos[i];
while (++i < pos.length)
pos[i]=pos[i-1]+1;
return true;
}
public void getSelection(List<?> l) {
@SuppressWarnings("unchecked")
List<Object> ll = (List<Object>)l;
if (ll.size()!=pos.length) {
ll.clear();
for (int i=0; i < pos.length; ++i)
ll.add(set.get(pos[i]));
}
else {
for (int i=0; i < pos.length; ++i)
ll.set(i, set.get(pos[i]));
}
}
}
用法示例:
static void main(String[] args) {
List<Character> l = new ArrayList<Character>();
for (int i=0; i < 32; ++i) l.add((char)('a'+i));
Combinations comb = new Combinations(l,5);
int n=0;
do {
++n;
comb.getSelection(l);
//Log.debug("%d: %s", n, l.toString());
} while (comb.next());
Log.debug("num = %d", n);
}
也许我错过了重点(你需要的是算法,而不是现成的解决方案),但看起来scala已经开箱即用了(现在):
def combis(str:String, k:Int):Array[String] = {
str.combinations(k).toArray
}
使用这样的方法:
println(combis("abcd",2).toList)
会产生:
List(ab, ac, ad, bc, bd, cd)
简单但缓慢的c++回溯算法。
#include <iostream>
void backtrack(int* numbers, int n, int k, int i, int s)
{
if (i == k)
{
for (int j = 0; j < k; ++j)
{
std::cout << numbers[j];
}
std::cout << std::endl;
return;
}
if (s > n)
{
return;
}
numbers[i] = s;
backtrack(numbers, n, k, i + 1, s + 1);
backtrack(numbers, n, k, i, s + 1);
}
int main(int argc, char* argv[])
{
int n = 5;
int k = 3;
int* numbers = new int[k];
backtrack(numbers, n, k, 0, 1);
delete[] numbers;
return 0;
}
下面是c++中的迭代算法,它不使用STL,也不使用递归,也不使用条件嵌套循环。这样更快,它不执行任何元素交换,也不会给堆栈带来递归负担,还可以通过分别用mallloc()、free()和printf()替换new、delete和std::cout轻松地移植到ANSI C。
如果你想用不同或更长的字母显示元素,那么改变*字母参数以指向不同于"abcdefg"的字符串。
void OutputArrayChar(unsigned int* ka, size_t n, const char *alphabet) {
for (int i = 0; i < n; i++)
std::cout << alphabet[ka[i]] << ",";
std::cout << endl;
}
void GenCombinations(const unsigned int N, const unsigned int K, const char *alphabet) {
unsigned int *ka = new unsigned int [K]; //dynamically allocate an array of UINTs
unsigned int ki = K-1; //Point ki to the last elemet of the array
ka[ki] = N-1; //Prime the last elemet of the array.
while (true) {
unsigned int tmp = ka[ki]; //Optimization to prevent reading ka[ki] repeatedly
while (ki) //Fill to the left with consecutive descending values (blue squares)
ka[--ki] = --tmp;
OutputArrayChar(ka, K, alphabet);
while (--ka[ki] == ki) { //Decrement and check if the resulting value equals the index (bright green squares)
OutputArrayChar(ka, K, alphabet);
if (++ki == K) { //Exit condition (all of the values in the array are flush to the left)
delete[] ka;
return;
}
}
}
}
int main(int argc, char *argv[])
{
GenCombinations(7, 4, "abcdefg");
return 0;
}
重要提示:字母参数*必须指向至少N个字符的字符串。你也可以传递一个在其他地方定义的字符串地址。
组合:从“7选4”中选择。
简短的java解决方案:
import java.util.Arrays;
public class Combination {
public static void main(String[] args){
String[] arr = {"A","B","C","D","E","F"};
combinations2(arr, 3, 0, new String[3]);
}
static void combinations2(String[] arr, int len, int startPosition, String[] result){
if (len == 0){
System.out.println(Arrays.toString(result));
return;
}
for (int i = startPosition; i <= arr.length-len; i++){
result[result.length - len] = arr[i];
combinations2(arr, len-1, i+1, result);
}
}
}
结果将是
[A, B, C]
[A, B, D]
[A, B, E]
[A, B, F]
[A, C, D]
[A, C, E]
[A, C, F]
[A, D, E]
[A, D, F]
[A, E, F]
[B, C, D]
[B, C, E]
[B, C, F]
[B, D, E]
[B, D, F]
[B, E, F]
[C, D, E]
[C, D, F]
[C, E, F]
[D, E, F]