[c++] naloge

1. Imamo n učencev in m tem tako da je m manjši ali enak n. Moremo razdelit teme med učence, tako da nobena tema ne ostane. Kake so vse možnosti in koliko jih je?
Primer: n = 3, m =2
1 1 2
1 2 1
1 2 2
2 2 1
2 1 2
2 1 1
Število rešitev je 6.

ivana213 je 21. jun 2014 ob 16:30 izjavil:

Zdravo!

Jaz bi prosla za pomoč pri naslednjih dveh nalogah, če bi kdo znal. Tudi samo kakšna pseudokoda ali ideja bi mi zelo pomagali :)

1. Imamo n učencev in m tem tako da je m manjši ali enak n. Moremo razdelit teme med učence, tako da nobena tema ne ostane. Kake so vse možnosti in koliko jih je?
Primer: n = 3, m =2
1 1 2
1 2 1
1 2 2
2 2 1
2 1 2
2 1 1
Število rešitev je 6.

2. Dana je množice elementov, kjer se lahko elementi ponavljajo. Zato lahko ima množica z elementi tudi manj kot n! permutacija.
Na primer. Vhodni podatek je množica 1, 1, 2, 2. Njene permutacije so
1 1 2 2
1 2 1 2
1 2 2 1
2 1 1 2
2 1 2 1
2 2 1 1

function cuboid(inserted_cuboids, leftover_cuboids) {
  if(leftover_cuboids.length < 1) {
    return inserted_cuboids;
  } else {
    if(evaluate_inserted_cuboids()) return; // če ne ustreza pogojem
  
    for(cuboid in leftover_cuboids) {
      var permutes = cuboid.permute() // vrne array permutacij
      var new_leftover = leftover_cuboids.without(cuboid);

      for(permute in permutes){
         cuboid(inserted_cuboids.push(permute), new_leftover);
      }
    }
  }
}

Spura je 1. jul 2014 ob 19:17 izjavil:

Ce bi bil dejansko prav napisan, bi to bil algoritem s sestopanjem (backtrackingom) s casovno zahtevnostjo O(2^n).

technolog je 1. jul 2014 ob 21:28 izjavil:

Spura je 1. jul 2014 ob 20:18 izjavil:

Dynamic programming je drugace eno zelo butasto ime za divide and conquer algoritme.

Sploh ne. Dinamično programiranje pa divide and conquer sta dve čisto drugi paradigmi.

technolog je 1. jul 2014 ob 21:28 izjavil:

Rešitev tretje naloge pa je taka:

Najprej posortiraš vse koordinate po velikosti, to ti omogoči, da v O(n) ugotoviš, če kocka paše ena v drugo. O(k*n*logn)

Potem v O(n*k^2) zgradiš graf, katera kocka pade v katero. Ta graf je jasno usmerjeno drevo.

Nato pa lahko v času O(k^2) ugotoviš premer usmerjenega drevesnega grafa (najdaljšo mogočo pot).

Skupaj: O(n*k*logn + n*k^2)

alexa-lol je 1. jul 2014 ob 21:07 izjavil:

Spura je 1. jul 2014 ob 19:17 izjavil:

Ce bi bil dejansko prav napisan, bi to bil algoritem s sestopanjem (backtrackingom) s casovno zahtevnostjo O(2^n).

Kaj sem falil?

n = 5
m = 3

(1..n).to_a.combination(m).each { |com|
	(1..m).to_a.repeated_permutation(n-m).each { |perm|
		j = -1
		p Array.new(n) { |i|
			if idx = com.index(i+1)
				idx + 1
			else
				j += 1
				perm[j]
			end
		}
	}
}

technolog je 1. jul 2014 ob 20:30 izjavil:

Koda od uporabnika @Randomness je slaba, ker v primeru, ko je n = m, je časovna zahtevnost moje kode O(1), njegove pa O(n^n). Podobno slabo za vse primere, ko je m blizu n.

// kombinatorične kompozicije dolžine n
def comp(n: Int, t: Int): Seq[List[Int]] = {
	if (n == 1) Seq(List(t)) else for {
		x <- 1 to t-n+1
		c <- comp(n-1, t-x)
	} yield x :: c
}

// permutacije z ekvivalenčnimi skupinami
def pos(rem: List[(Int, Int)]) = {
	def posRec(rem: List[(Int, Int)], cur: List[Int]): Seq[List[(Int, Int)]] = {
		if (rem.isEmpty) Seq(List()) else {
			val (num, p) = rem.head
			for {
				comb <- cur.combinations(num).toSeq
				tail <- posRec(rem.tail, cur diff comb)
			} yield (comb zip Stream.continually(p+1)) ++ tail
		}
	}

	val size = rem.map(_._1).sum
	posRec(rem, (0 until size).toList).map(
		_.sorted.map(_._2)
	)
}


def prva(n: Int, m: Int) = {
	require(m <= n, "Število študentov mora biti manj kot nalog.")
	comp(m, n).flatMap(x => pos(x.zipWithIndex))
}

def druga(nums: Int*) = {
	pos(nums.groupBy(identity).toList.map { case (n, all) =>
		all.size -> (n-1)
	}).toVector
}

println(prva(3,2))
println(druga(1,1,2,2,3))

import java.util.Arrays;

/**
 *
 * @author
*/

public class Naloga1 {
    public static void main(String[] args) {
        long t = System.nanoTime();
        print(3,5);
        System.out.println(System.nanoTime() - t);
    }
    
    
    private static void print(int numOfTopics, int numOfPeople) {
        int[] handedOut = new int[numOfTopics];
        int[] assigments = new int[numOfPeople];
        print(handedOut, assigments, 0, numOfTopics);
    }
    
    private static void print(int[] handedOut, int[] assigments, int idx, int zeroes) {
        for (int i = 0;i < handedOut.length;i++) {
            assigments[idx] = i + 1;
            if (handedOut[i]++ == 0) {
                zeroes-- ;
            }
            if (zeroes == 0) {
                enumerate(assigments, idx + 1, handedOut.length);
            } else if (zeroes < assigments.length - idx) {
                print(handedOut, assigments, idx+1, zeroes);
            } 
            if (handedOut[i]-- == 1) {
                zeroes++;
            }
        }
    }
    
    private static void enumerate(int[] assigments, int idx, int maxElem) {
        if (idx == assigments.length) {         
            System.out.println(Arrays.toString(assigments));
        } else {
            for (int i = 1;i <= maxElem;i++) {
                assigments[idx] = i;
                enumerate(assigments, idx + 1, maxElem);
            }
        }
    }
}

package main

import _ "fmt"

func main() {
	razdeli(7, 11)
}

func reverse(a []int) {
	for i := 0; i < len(a)/2; i++ {
		a[i], a[len(a)-i-1] = a[len(a)-i-1], a[i]
	}
}

func permNext(a []int) bool {
	for i := len(a) - 2; i >= 0; i-- {
		if a[i] < a[i+1] {
			for j := len(a) - 1; j > i; j-- {
				if a[i] < a[j] {
					a[i], a[j] = a[j], a[i]
					break
				}
			}
			reverse(a[i+1 : len(a)])
			return true
		}
	}
	return false
}

func gen(a, p []int, m int) {
	for i, j, k := 1, 0, 0; i <= m; i++ {
		for ; j < len(p) && p[j] <= i; j++ {
			a[k] = p[j]
			k++
		}
		a[k] = i
		k++
	}

	//fmt.Println(a)
	for permNext(a) == true {
		//fmt.Println(a)
	}
}

func permIncreasingNext(p []int, m int) bool {
	if p[0] == m && p[len(p)-1] == m {
		return false
	}

	i := len(p) - 1
	for ; p[i] == m; i-- {

	}

	v := p[i] + 1
	p[i] = v
	for i = i + 1; i < len(p); i++ {
		p[i] = v
	}

	return true
}

func razdeli(m, n int) {
	a := make([]int, n)
	if n > m {
		p := make([]int, n-m)

		for i := 0; i < len(p)-1; i++ {
			p[i] = 1
		}
		p[len(p)-1] = 0

		for permIncreasingNext(p, m) == true {
			gen(a, p, m)
		}
	} else {
		gen(a, []int{}, m)
	}
}