Занятие 3. Справочник

Занятие 3. Справочник

Генерация всех сочетаний из N по M 
import java.io.*;
import java.util.*;

public class Gen
{
	static PrintWriter out = new PrintWriter(System.out);
	
	static int[] K;
	static int  N, M; 
	
	static void print(int n)
	{
		for (int i = 0; i < n; i++)
		{
			out.print(K[i] + " ");
		}	
		out.println();
	}
	
	static void gen(int k)
	{
	  if (k == M) print(M);
	  else
	  {	  
		  int start = 1;
		  if (k > 0) start = K[k-1] + 1;
		  for (int i = start; i <= N; i++)
		  {    
			  K[k] = i;
			  gen(k + 1);
		  }
	   }	  
	 }
		
	public static void main(String[] args) throws IOException
	{
		Scanner in = new Scanner(System.in);
	        N = in.nextInt();
	        M = in.nextInt();
		K = new int[M];

		gen(0);
		out.flush();
         }
}
Генерация всех перестановок 
static void gen(int k)
{
  if (k == M) print(M);
  else
  {
	for (int i = 1; i <= N; i++)
	{    
		  if (found(i, k)) continue; 
		  K[k] = i;
		  gen(k + 1);
	}
  }
}
Она использует функцию found, Которая ищет значение v среди первых n элементов массива K 
static boolean found(int v, int n)
{
	for (int i = 0; i < n; i++)
	{
		if (K[i] == v) return true;
	}	
	return false;
}
Генерация следующей перестановки 
static void swap(int p[], int i, int j){
     int tmp = p[i];
     p[i] = p[j];
     p[j] = tmp;
}
static void reverse(int p[], int l){
    int r = p.length - 1;
    for(; l < r; l++, r--){
        swap(l, r);
    }
}

static boolean generateNextPermutation(int[] p) {
    int k = p.length - 2;
    while(k >= 0 && p[k] >= p[k + 1]){
        k--;
    }
    if(k == -1){
        return false;
    }
    int t = p.length - 1;
    while(p[t] <= p[k]){
        t--;
    }
    swap(t, k);
    reverse(k + 1);
    return true;
}
Генерация следующей анаграммы 
private String getNext(String s) 
{
// Удобно проводить операции с массивом символов,
// а не с объектами класса String.
char a[] = s.toCharArray();

	int n = a.length;
	int k = a.length-2;
	if (k < 0)
		return new String(a);
	while(a[k] >= a[k+1]){
		k--;
		if (k == -1){
			Arrays.sort(a);
			return new String(a);
		}
	}
	int t = -1;
	for(int i=k+1;i a[k] && (t == -1 || a[t] > a[i])){
			t = i;
		}
	}
	
	char tmp = a[k];
	a[k] = a[t];
	a[t] = tmp;

	Arrays.sort(a, k + 1, n);

	return new String(a);
}
Перестановка по номеру 
k--;
boolean used[] = new boolean[n];
for (int i = 0; i < n; i++) used[i] = false;
for (int i = 0; i < n; i++)
{
    int j = 0;
    while (used[j]) j++;
    while (k >= fact(n - i - 1)){
        j++;
        k -= fact(n - i - 1);
        while (used[j]) j++;
    }
    used[j] = true;
    out.print((j + 1) + " ");
}
Номер размещения 
long res = 1;
int to = k;
for (int i = 1; i <= to; i++)
{
	int x;
	x = in.nextInt();
	for (int j = 1; j < x; j++) {
		if (used[j])
			continue;
		res += fact(n – i) / fact(n - i - k + 1);
	}
	used[x] = 1;
	k--;
}