下列高亮的术语将对你完成今天的挑战非常有用.
也许你已经注意到, 从事件发生的可能性中发现规律,非常利于我们从样本空间中计算所求事件的数量. 有两种这么做的最简单的方法是, 用排列(permutation, 有顺序)和组合(combination, 顺序无关).
排列 Permutation
注: 其实排列是Arrangement, 全排列才是Permutation?
从一个n个元素的集合A中, 取r个对象的有序排列(注, 有序,例如a,b和b,a这两个是不一样的), (其中0 < r ≤ n), 这就叫一个A集合的r元素排列. 你也可以把这当作A的全排列中一次取r个元素的排列. 一个n元素的集合的r元素排列的数量可以表示为以下公式:
注意: 我们定义0!的值为1, 否则的话, nPn就成了n!/(n-n)! → n!/0!
组合 Combinations
从一个n个元素的集合A中, 取r个对象的无序排列(注, 无序,例如a,b和b,a这两个是一样的,只有有a有b就行), (其中0 < r ≤ n), 这就叫一个A集合的r元素组合.
因为排列和组合的唯一区别就是组合是无序的. 我们通过从排列中约去r的全排列(r!):
当我们说到组合时, 我们指n元素集合中取出r元素的子集的可能取法的数量. 实际上, nCr通常被称为"n选r". 因为, 这个就是计算n元素集合中取出r元素的子集有多少可能取法.
nCr也通常写成
求1,2...n的r排列
假设有n=6元素集合1, 2, 3, 4, 5, 6, 求r=3的所有排列, 例如:
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
1,2,4
1,4,2
.......
输入约束
- 0 < n ≤ 10
- 0 < r ≤ n
输出示例
例如1 ~ 9中取5个元素的所有组合
1 [1, 2, 3, 4, 5]
2 [1, 2, 3, 4, 6]
3 [1, 2, 3, 4, 7]
4 [1, 2, 3, 4, 8]
......
126 [5, 6, 7, 8, 9]
注:这个题我自己出的,我看了一下hackrank好像没有找到这道题.....
java + 递归
public class CombinationTest {
static ConcurrentLinkedQueue<Collection<Integer>> buf = new ConcurrentLinkedQueue<>();
private static void collect(Collection<Integer> combination) {
buf.offer(combination);
}
static void iterateForCombination(List<Integer> src, Collection<Integer> combination, int c) {
if (c == 1) {
for (Integer e : src) {
final ArrayList<Integer> _combination = copyOnAppend(combination, e);
collect(_combination);
}
return;
}
for (int i = 0, j = src.size(); i < j; i++) {
if (j - i <= c) {
combination.addAll(src.subList(i, src.size()));
collect(combination);
break;
}
final Integer e = src.get(i);
final ArrayList<Integer> _combination = copyOnAppend(combination, e);
iterateForCombination(src.subList(i + 1, j), _combination, c - 1);
}
}
private static ArrayList<Integer> copyOnAppend(Collection<Integer> combination, Integer e) {
final ArrayList<Integer> _combination = new ArrayList<>(combination.size() + 1);
_combination.addAll(combination);
_combination.add(e);
return _combination;
}
public static void main(String[] args) {
List<Integer> list = IntStream.range(1, 6).mapToObj(Integer::valueOf).collect(Collectors.toList());
System.out.println(list);
int r = 3;
iterateForCombination(list, new ArrayList<>(), r);
buf.forEach(combination -> System.out.printf("%s\n", combination));
}
}
java + ForkJoinTask
public class CombinationTest {
static ConcurrentLinkedQueue<Collection<Integer>> buf = new ConcurrentLinkedQueue<>();
private static void collect(Collection<Integer> combination) {
buf.offer(combination);
}
private static void iterateForCombinationsWithForkJoin(List<Integer> list, int r) {
final CombinationTask ct = new CombinationTask(list, new ArrayList<>(r), r);
ct.invoke();
try { ct.join(); } catch (Exception e) { e.printStackTrace(); }
}
static class CombinationTask extends RecursiveAction {
List<Integer> src;
Collection<Integer> combination;
int c;
public CombinationTask(List<Integer> list, Collection<Integer> combination, int c) {
this.src = list;
this.combination = combination;
this.c = c;
}
@Override
protected void compute() {
if (c == 1) {
for (Integer e : src) {
final ArrayList<Integer> _combination = copyOnAppend(this.combination, e);
collect(_combination);
}
return;
}
List<CombinationTask> taskList = new ArrayList<>(c);
for (int i = 0, j = src.size(); i < j; i++) {
if (j - i <= c) {
combination.addAll(src.subList(i, j));
collect(combination);
break;
}
final Integer e = src.get(i);
final ArrayList<Integer> _combination = copyOnAppend(this.combination, e);
taskList.add(new CombinationTask(src.subList(i + 1, j), _combination, c - 1));
}
invokeAll(taskList);
}
}
private static ArrayList<Integer> copyOnAppend(Collection<Integer> combination, Integer e) {
final ArrayList<Integer> _combination = new ArrayList<>(combination.size() + 1);
_combination.addAll(combination);
_combination.add(e);
return _combination;
}
public static void main(String[] args) {
List<Integer> list = IntStream.range(1, 6).mapToObj(Integer::valueOf).collect(Collectors.toList());
System.out.println(list);
int r = 3;
iterateForCombinationsWithForkJoin(list, r);
buf.forEach(combination -> System.out.printf("%s\n", combination));
}
}
java + 栈 + 循环
public class CombinationTest {
static ConcurrentLinkedQueue<Collection<Integer>> buf = new ConcurrentLinkedQueue<>();
private static void collect(Collection<Integer> combination) {
buf.offer(combination);
}
static class StackFrame {
List<Integer> src;
Collection<Integer> combination;
int c;
public StackFrame(List<Integer> list, Collection<Integer> combination, int c) {
this.src = list;
this.combination = combination;
this.c = c;
}
}
static void iterateForCombinationWithStack(List<Integer> _src, int _c) {
ArrayDeque<StackFrame> stack = new ArrayDeque<>(1000000);
stack.push(new StackFrame(_src, new ArrayList<>(_c), _c));
while (!stack.isEmpty()) {
StackFrame sf = stack.pop();
List<Integer> src = sf.src;
int c = sf.c;
Collection<Integer> combination = sf.combination;
if (c == 1) {
for (Integer e : src) {
final ArrayList<Integer> _combination = copyOnAppend(combination, e);
collect(_combination);
}
continue;
}
for (int _i = 0, j = src.size(); _i < j; _i++) {
if (j - _i <= c) {
combination.addAll(src.subList(_i, src.size()));
collect(combination);
break;
}
final Integer e = src.get(_i);
final ArrayList<Integer> _combination = copyOnAppend(combination, e);
stack.push(new StackFrame(src.subList(_i + 1, j), _combination, c - 1));
}
}
}
private static ArrayList<Integer> copyOnAppend(Collection<Integer> combination, Integer e) {
final ArrayList<Integer> _combination = new ArrayList<>(combination.size() + 1);
_combination.addAll(combination);
_combination.add(e);
return _combination;
}
public static void main(String[] args) {
List<Integer> list = IntStream.range(1, 6).mapToObj(Integer::valueOf).collect(Collectors.toList());
System.out.println(list);
int r = 3;
iterateForCombinationWithStack(list, r);
buf.forEach(combination -> System.out.printf("%s\n", combination));
}
}
Scala 代码好特么简洁啊!!!!
@Test def combinations(): Unit = {
val list: List[Int] = 1 to 5 toList
val r: Int = 3
val buf: ConcurrentLinkedQueue[List[Int]] = new ConcurrentLinkedQueue[List[Int]]()
def iterateForCombination(src: List[Int], combination: List[Int], c: Int): Unit = {
if (c == 1) {
src.foreach(e => buf.offer(e +: combination))
return
}
val j: Int = src.size
for (i <- 0 to j) {
if (j - i <= c) {
buf.offer(combination ++ src.slice(i, j))
return
}
iterateForCombination(src.slice(i + 1, j), src(i) +: combination, c - 1)
}
}
iterateForCombination(list, List.empty[Int], r)
import collection.JavaConverters._
buf.asScala.zipWithIndex.foreach(line => println(s"${line._2}\t ${line._1.mkString(", ")}"))
}
python 和scala差不多的感觉
def combinations():
_list = list(range(1, 6))
print(_list)
r = 3
buf = []
def iterate_for_combinations(src, combination=[], c=r):
if c == 1:
for e in src:
buf.append(combination + [e])
return
j = len(src)
for i in range(0, j):
if j - i <= c:
buf.append(combination + src[i:j])
return
iterate_for_combinations(src[i + 1:j], combination + [src[i]], c - 1)
iterate_for_combinations(_list)
for c in buf:
print(c)
if __name__ == '__main__':
combinations()
