현재 위치

홈 ›› Forums ›› 재미 ›› 자유 게시판

알고리듬 질문...

지리즈의 이미지
글쓴이: 지리즈 / 작성시간: 화, 2009/09/29 - 11:17오전

1,2,3,4,5..n 이런 수열이 있을때,이 수들을 나열할 수 있는 조합의 수는 n!(패토리얼)입니다.

1,2,3 일 경우 3! {1,2,3} {1,3,2} {3,1,2} {2,1,3} {2,3,1} {3,2,1} 의 6개이죠.

n의 수열이 있을 때 위의 조합의 배열을 구하는 적절한 알고리듬을 알고 계시는 분 도움 부탁드립니다.

패토리얼의 값을 구하는 것이 아니라, 수들의 나열 할 수 있는 조합인 n!개의 배열을 구하는 것입니다.

Forums: 
자유 게시판
lifthrasiir의 이미지

글쓴이: lifthrasiir / 작성시간: 화, 2009/09/29 - 11:22오전

C++ std::next_permutation 갈은 걸 찾아 보시면 도움이 될 겁니다.

ckebabo의 이미지

글쓴이: ckebabo / 작성시간: 화, 2009/09/29 - 12:23오후

python 버전...

얼마전에 어떤 싸이트를 참고해서 작성해 놓은건데 정작 그 싸이트는 잘 기억이 안나네요...

def next_permutation(seq, comp=cmp):
    if not seq:
        raise StopIteration
 
    try:
        seq[0]
    except TypeError:
        raise TypeError("seq must allow random access.")
 
    length = len(seq)
 
    yield seq[:]
 
    if length == 1:
        raise StopIteration
 
    while True:
        # Step 1
        j = length - 2
        while not (comp(seq[j], seq[j+1]) < 0):
            j -= 1
            if j<0:
                raise StopIteration
 
        # Step 2
        m = length - 1
        while not (comp(seq[j], seq[m]) < 0):
            m -= 1
        seq[j], seq[m] = seq[m], seq[j]
 
        # Step 3
        left = j+1
        right = length - 1
        while left < right:
            seq[left], seq[right] = seq[right], seq[left]
            left += 1
            right -= 1
 
        yield seq[:]
 
    raise StopIteration
 
for permutation in next_permutation(range(1,3+1)):
    print permutation

litiblue의 이미지

글쓴이: litiblue / 작성시간: 화, 2009/09/29 - 6:06오후

int a[3];
int chk[4];

void perm(int level)
{
int i;

if (level == 3) {
배열 a를 프린트;
return;
}

for (i=1; i<=3; i++) {
if (chk[i]) continue;

a[level] = i;
chk[i] = 1;
perm (level + 1);
chk[i] = 0;
}
}

int main(void)
{
perm(0);
}

^^

rgbi3307의 이미지

글쓴이: rgbi3307 / 작성시간: 수, 2009/09/30 - 2:12오후

for 루프안에서 중복요소를 제거하기 위한 문장인
if (chk[i]) continue;
이거 이해 하는데, 한참 걸렸네요.
좋은 코드인듯 합니다.
감사해요~

아참, 제가 위의 코드를 테스트 한것을 덧붙입니다.

#include <stdio.h>
 
int A[3];
int Achk[4];
//int icnt = 0;
 
void array_print (int *A, int num)
{
	int	i;
	for (i = 0; i < num; i++)
		printf ("%d, ", A[i]);
	printf ("\n");
}
 
void perm(int level)
{
	int i;
 
	if (level == 3) {
		array_print (A, 3);
		return;
	}
 
	for (i = 0; i < 3; i++) {
		//icnt++;
		if (Achk[i]) continue;
 
		A[level] = i + 1;
		Achk[i] = 1;
		perm (level + 1);
		Achk[i] = 0;
	}
}
 
int main(void)
{
	perm(0);
 
	//_getch();
}

From:
*알지비 (메신저: rgbi3307(at)nate.com)
*학창시절 마이크로마우스를 만들었고, 10년동안 IT관련 개발자로 일하고 있음.
*틈틈히 커널연구회(http://www.kernel.kr/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))

From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))

purluno의 이미지

글쓴이: purluno / 작성시간: 화, 2009/09/29 - 1:48오후

Scala (programming language)

object Permut {
  def permut&#91;A](list: List&#91;A]): List&#91;List&#91;A]] = {
    if (list.isEmpty) {
      List(Nil)
    } else {
      for {
        e <- list
        p <- permut(list - e)
      } yield e :: p
    }
  }
 
  def main(args: Array&#91;String]): Unit = {
    val list = List("A", "B", "C", "D")
    println(permut(list))
  }
}

결과

List(List(A, B, C, D), List(A, B, D, C), List(A, C, B, D), List(A, C, D, B), List(A, D, B, C), List(A, D, C, B), List(B, A, C, D), List(B, A, D, C), List(B, C, A, D), List(B, C, D, A), List(B, D, A, C), List(B, D, C, A), List(C, A, B, D), List(C, A, D, B), List(C, B, A, D), List(C, B, D, A), List(C, D, A, B), List(C, D, B, A), List(D, A, B, C), List(D, A, C, B), List(D, B, A, C), List(D, B, C, A), List(D, C, A, B), List(D, C, B, A))

winner의 이미지

글쓴이: winner / 작성시간: 화, 2009/09/29 - 2:24오후

(A, B, B, C)로 나타낼 수 있는 순열을 찾는다면 이야기는 조금 복잡해지니까요.
그런 것을 고려한다면 확실히 C++ std::next_permutation만한게 없을 것 같습니다.

중복이 없다면 순열생성은 생각만큼 어렵지는 않으니까 직접 작성하시는 것도 괜찮을 것 같고요.
next_permutation 보다 일반적인 재귀호출을 쓰는게 순열을 모두 생성할 때는 조금은 성능이 좋습니다.

superwtk의 이미지

글쓴이: superwtk / 작성시간: 화, 2009/09/29 - 3:50오후

재귀적으로 비교적 간단히 표현할 수 있는데, LaTeX 편집기가 작동이 안되는 관계로 파이썬 코드로 대체하겠습니다-_-a

def permutation(set):
        if set == []:
                return [[]]
        else:
                r = []
                for i in xrange(0, len(set)):
                        for p in permutation(set[0:i] + set[i+1:]):
                                r.append([set[i]] + p)
                return r
 
 
print permutation([1,2,3,4])

실행 결과

[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]]

--------------------------------------------------------------------------------
http://blog.sumin.us

7339989b62a014c4ce6e31b3540bc7b5f06455024f22753f6235c935e8e5의 이미지

글쓴이: 7339989b62a014c... / 작성시간: 화, 2009/09/29 - 5:49오후

파이썬 모듈 itertools를 사용하면 간단합니다.

import itertools
N = 3
for seq in itertools.permutations(xrange(1, N + 1)):
  print seq

파이썬 만세!

---8< 서명 -----------------
애니메이션 감상 기록 http://animeta.net/

김전일의 이미지

글쓴이: 김전일 / 작성시간: 화, 2009/09/29 - 11:32오후

printperm(P,S)
/* P is a prefix, S is a nonempty set */
/* call it with P empty initially */

if S has 1 element
then print P followed by the single element of S

else
for each element i of S do
printperm( (P,i), S - {i})

지리즈의 이미지

글쓴이: 지리즈 / 작성시간: 수, 2009/09/30 - 12:23오전

이게 업무에 관련된 것은 아니고...
와우의 징벌기사 딜매크로 생성하는데 필요해서요. ㅎㅎㅎ
그래서, 개발언어가 상당히 자유롭습니다.

현재는 qt 콘솔어플리케이션으로 개발되고 있는 중인데,
주로 사용하는 5가지 기술(신성화,성전사의 일격,심판,천상의 폭풍,퇴마술)에 대한
FCFS(First Come First Serve)는 구현되었습니다. 문제는 매크로 사이즈가 255자를 넘어가면 안됩니다.
이 제한된 매크로내에서 최대 효율을 뽑으려면,
위 5가지 기술을 어떤 순서대로 사용할지가 관건이 됩니다.
그래서, 모든 경우의 가지수에 대해서 통계를 뽑아보고, 가장 효율이 좋은 넘을 쓸려구요.

답글 주신 내용을 검토해서 적용해보고
쓸만해지면... kldp.net에 올릴께요~ ㅎ

There is no spoon. Neo from the Matrix 1999.

There is no spoon. Neo from the Matrix 1999.

purluno의 이미지

글쓴이: purluno / 작성시간: 수, 2009/09/30 - 12:47오전

Scala - 순열, 중복순열, 조합, 중복조합

object Permutation {
  // 순열
  def permutations&#91;A](lst: List&#91;A], n: Int): List&#91;List&#91;A]] =
    if (n <= 0) List(Nil)
    else for (e <- lst; p <- permutations(lst - e, n - 1)) yield e :: p
 
  // 중복순열
  def repermutations&#91;A](lst: List&#91;A], n: Int): List&#91;List&#91;A]] =
    if (n <= 0) List(Nil)
    else for (e <- lst; p <- repermutations(lst, n - 1)) yield e :: p
 
  // 조합
  def combinations&#91;A](lst: List&#91;A], n: Int): List&#91;List&#91;A]] =
    if      (n <= 0)       List(Nil)
    else if (lst.isEmpty)  Nil
    else combinations(lst.tail, n - 1).map(lst.head :: _) ::: combinations(lst.tail, n)
 
  // 중복조합
  def recombinations&#91;A](lst: List&#91;A], n: Int): List&#91;List&#91;A]] =
    if      (n <= 0)       List(Nil)
    else if (lst.isEmpty)  Nil
    else recombinations(lst, n - 1).map(lst.head :: _) ::: recombinations(lst.tail, n)
 
  def main(args: Array&#91;String]): Unit = {
    val list = List("A", "B", "C", "D")
    println("For " + list)
    println
    println("Permutations / select 2 elements")
    println(permutations(list, 2))
    println
    println("Permutations with repetition / select 2 elements")
    println(repermutations(list, 2))
    println
    println("Combinations / select 2 elements")
    println(combinations(list, 2))
    println
    println("Combinations with repetition / select 2 elements")
    println(recombinations(list, 2))
    println
  }
}

결과

For List(A, B, C, D)
 
Permutations / select 2 elements
List(List(A, B), List(A, C), List(A, D), List(B, A), List(B, C), List(B, D),
     List(C, A), List(C, B), List(C, D), List(D, A), List(D, B), List(D, C))
 
Permutations with repetition / select 2 elements
List(List(A, A), List(A, B), List(A, C), List(A, D), List(B, A), List(B, B),
     List(B, C), List(B, D), List(C, A), List(C, B), List(C, C), List(C, D),
     List(D, A), List(D, B), List(D, C), List(D, D))
 
Combinations / select 2 elements
List(List(A, B), List(A, C), List(A, D), List(B, C), List(B, D), List(C, D))
 
Combinations with repetition / select 2 elements
List(List(A, A), List(A, B), List(A, C), List(A, D), List(B, B), List(B, C),
     List(B, D), List(C, C), List(C, D), List(D, D))

imyejin의 이미지

글쓴이: imyejin / 작성시간: 수, 2009/09/30 - 2:47오전 

permutations :: [a] -> [[a]]
permutations []     = [[]]
permutations (x:xs) = [zs | ys <- permutations xs, zs <- everywhere x ys]
 
everywhere :: a -> [a] -> [[a]]
everywhere x []     = [[x]]
everywhere x (y:ys) = (x:y:ys) : [y:zs | zs <- everywhere x ys]

출처는 http://davidtran.doublegifts.com/blog/?cat=2

[예진아씨 피카사 웹앨범] 임예진 팬클럽 ♡예진아씨♡ http://cafe.daum.net/imyejin

[예진아씨 피카사 웹앨범] 임예진 팬클럽 ♡예진아씨♡ http://cafe.daum.net/imyejin

siabard의 이미지

글쓴이: siabard / 작성시간: 수, 2009/09/30 - 8:23오전 

(defun permute (lst)
  (cond ((null lst) (list nil))
		((atom lst) (list (list lst)))
		((= (length lst) 1) (list lst))
		(t
		 (let ((result nil))
		   (dolist (x lst)
			 (setf result
				   (union result 
						  (mapcar #'(lambda (l) (cons x l))
								  (permute (remove x lst))))))
		   result))))

--
새로움을 느끼기에 삶은 즐겁다..
모험가 아돌 크리스틴을 꿈꾸며..
Sia..

새로움을 느끼기에 삶은 즐겁다..
모험가 아돌 크리스틴을 꿈꾸며..
Sia..

둘러보기