[BOJ] 10974 모든 순열

https://www.acmicpc.net/problem/10974

using System;
using System.IO;
using System.Linq;
using System.Text;

namespace ConsoleApp4
{
    class Program
    {
        static void swap(ref int n1, ref int n2)
        {
            int tmp = n1;
            n1 = n2;
            n2 = tmp;
        }
        static bool next_permutaion(int[] arr, int n)
        {
            int i = n - 1;

            while(i>0 && arr[i-1] >= arr[i]) i--;

            if(i <= 0) return false;
            
            int j = n - 1;
            while(j>0 && arr[i-1] >= arr[j]) j--;
            
            swap(ref arr[i - 1], ref arr[j]);
            j = n - 1;

            for (; i < j; i++, j--) 
                swap(ref arr[i], ref arr[j]);
            return true; 
        }
        public static void Main(String[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int n = int.Parse(Console.ReadLine());

            int[] arr = new int[n];

            for(int i=0; i<n; i++)
            {
                arr[i] = i + 1;
            }

            StringBuilder sb = new StringBuilder();
            do
            {
                foreach(var num in arr)
                {
                    sb.Append(num + " ");
                }
                sb.AppendLine();
            } while (next_permutaion(arr, n));

            Console.WriteLine(sb.ToString());
            sw.Close();
            sr.Close();
        }
    }
}

 

 

 

c# 7.0 swap 

//(a[x], a[y]) = (a[y], a[x]);

 

 

linq

백준에서 시간초과 나옴...

using System;
using System.Collections.Generic;
using System.Linq;

namespace MakePermutation
{
    class Program
    {
        static void Main()
        {
            IEnumerable<IEnumerable<int>> result =
                GetPermutations(Enumerable.Range(1, 3), 3);
            foreach (var p in result)
            {
                foreach (var n in p)
                {
                    Console.Write("{0} ", n);
                }   
                Console.WriteLine();
            }
        }
        
        static IEnumerable<IEnumerable<T>>
            GetPermutations<T>(IEnumerable<T> list, int length)
        {
            if (length == 1) return list.Select(t => new T[] { t });

            return GetPermutations(list, length - 1)
                .SelectMany(t => list.Where(e => !t.Contains(e)),
                    (t1, t2) => t1.Concat(new T[] { t2 }));
        }
    }    
}

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;

namespace MakePermutation
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] items = new int[] { 1, 2, 3 };
            Permutation<int> p = new Permutation<int>(items);

            foreach (var result in p)
            {
                PrintElems(result);
            }
        }
        private static void PrintElems<T>(T[] elems)
        {
            //Console.Write("{ ");

            foreach (var elem in elems)
            {
                Console.Write(elem + ", ");
            }

            //Console.WriteLine("}");
            Console.WriteLine();
        }

    }
}



public class Permutation<TData> : IEnumerable<TData[]>
{
    private int[] data = null;
    private int order = 0;
    private TData[] elems;

    public Permutation(TData[] items)
    {
        this.order = items.Length;
        this.data = new int[this.order];
        this.elems = items;
        for (int i = 0; i < this.order; ++i)
        {
            this.data[i] = i;
        }
    }

    public Permutation<TData> Successor()
    {
        if (this.order <= 1)
        {
            return null;
        }

        Permutation<TData> result = new Permutation<TData>(this.elems);

        int left, right;
        for (int k = 0; k < result.order; ++k)  // Step #0 - copy current data into result
        {
            result.data[k] = this.data[k];
        }

        left = result.order - 2;  // Step #1 - Find left value 
        while ((result.data[left] > result.data[left + 1]) && (left >= 1))
        {
            --left;
        }

        if ((left == 0) && (this.data[left] > this.data[left + 1]))
        {
            return null;
        }

        right = result.order - 1;  // Step #2 - find right; first value > left
        while (result.data[left] > result.data[right])
        {
            --right;
        }

        int temp = result.data[left];  // Step #3 - swap [left] and [right]
        result.data[left] = result.data[right];
        result.data[right] = temp;

        int i = left + 1;              // Step #4 - order the tail
        int j = result.order - 1;

        while (i < j)
        {
            temp = result.data[i];
            result.data[i++] = result.data[j];
            result.data[j--] = temp;
        }

        return result;
    }

    internal static long Choose(int length)
    {
        long answer = 1;

        for (int i = 1; i <= length; i++)
        {
            checked { answer = answer * i; }
        }

        return answer;
    }

    public TData[] ApplyTo(TData[] arr)
    {
        if (arr.Length != this.order)
        {
            return null;
        }

        TData[] result = new TData[arr.Length];
        for (int i = 0; i < result.Length; ++i)
        {
            result[i] = arr[this.data[i]];
        }

        return result;
    }

    public override string ToString()
    {
        System.Text.StringBuilder sb = new System.Text.StringBuilder();

        sb.Append("( ");
        for (int i = 0; i < this.order; ++i)
        {
            sb.Append(this.data[i].ToString() + " ");
        }
        sb.Append(")");

        return sb.ToString();
    }

    public IEnumerator<TData[]> GetEnumerator()
    {
        Permutation<TData> p = new Permutation<TData>(this.elems);
        TData[] snapshot = null;

        while (p != null)
        {
            snapshot = p.ApplyTo(this.elems);
            yield return snapshot;

            p = p.Successor();
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        Permutation<TData> p = new Permutation<TData>(this.elems);
        TData[] snapshot = null;

        while (p != null)
        {
            snapshot = p.ApplyTo(this.elems);
            yield return snapshot;

            p = p.Successor();
        }
    }
}

 

using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Net;
using System.Net.Http;
using System.Net.Http.Headers;
using System.Text;

namespace _10974
{
    class Program
    {
        static void Main()
        {
            int n = Convert.ToInt32(Console.ReadLine());
            int[] arr = new int[n];

            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < n; i++) arr[i] = i+1;
            
            do
            {
                for (int i = 0; i < n; i++)
                    sb.Append(arr[i].ToString()+ " ");
                
                sb.Append("\n");
            } while (next_premutation(arr));

            Console.WriteLine(sb);
        }

        static bool next_premutation(int[] arr)
        {
            int i = arr.Length - 1;

            while (i > 0 && arr[i - 1] >= arr[i])
                i--;

            if (i <= 0)
                return false;

            int j = arr.Length - 1;

            while (arr[i - 1] >= arr[j])
                j--;

            (arr[i - 1], arr[j]) = (arr[j], arr[i - 1]); 

            j = arr.Length - 1;

            while(i < j)
            {
                (arr[i], arr[j]) = (arr[j], arr[i]);
                i++;
                j--;
            }

            return true;
        }
    }
}

 

 

 

https://www.sysnet.pe.kr/2/0/10955

https://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer