package com.jianggujin;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

/**
 * 水仙花數(shù)
 * 
 * @author jianggujin
 *
 */
public class NarcissusNumber
{
 /**
 * 記錄10的0~N次方
 */
 private BigInteger[] powerOf10;
 /**
 * 記錄0到9中任意數(shù)字i的N次方乘以i出現(xiàn)的次數(shù)j的結果（i^N*j）
 */
 private BigInteger[][] preTable1;
 /**
 * 記錄離PreTable中對應數(shù)最近的10的k次方
 */
 private int[][] preTable2;
 /**
 * 記錄0到9中每個數(shù)出現(xiàn)的次數(shù)
 */
 private int[] selected = new int[10];
 /**
 * 記錄水仙花數(shù)的位數(shù)
 */
 private int length;

 /**
 * 記錄水仙花數(shù)
 */
 private List<BigInteger> results;
 /**
 * 記錄當前的進制
 */
 private int numberSystem = 10;

 /**
 * @param n
 *   水仙花數(shù)的位數(shù)
 */
 private NarcissusNumber(int n)
 {
  powerOf10 = new BigInteger[n + 1];
  powerOf10[0] = BigInteger.ONE;
  length = n;
  results = new ArrayList<BigInteger>();

  // 初始化powerPowerOf10
  for (int i = 1; i <= n; i++)
  {
   powerOf10[i] = powerOf10[i - 1].multiply(BigInteger.TEN);
  }

  preTable1 = new BigInteger[numberSystem][n + 1];
  preTable2 = new int[numberSystem][n + 1];

  // preTable[i][j] 0-i的N次方出現(xiàn)0-j次的值
  for (int i = 0; i < numberSystem; i++)
  {
   for (int j = 0; j <= n; j++)
   {
   preTable1[i][j] = new BigInteger(new Integer(i).toString()).pow(n)
     .multiply(new BigInteger(new Integer(j).toString()));

   for (int k = n; k >= 0; k--)
   {
    if (powerOf10[k].compareTo(preTable1[i][j]) < 0)
    {
     preTable2[i][j] = k;
     break;
    }
   }
   }
  }
 }

 public static List<BigInteger> search(int num)
 {
  NarcissusNumber narcissusNumber = new NarcissusNumber(num);
  narcissusNumber.search(narcissusNumber.numberSystem - 1, BigInteger.ZERO, narcissusNumber.length);
  return narcissusNumber.getResults();
 }

 /**
 * @param currentIndex
 *   記錄當前正在選擇的數(shù)字(0~9)
 * @param sum
 *   記錄當前值（如選了3個9、2個8 就是9^N*3+8^N*2）
 * @param remainCount
 *   記錄還可選擇多少數(shù)
 */
 private void search(int currentIndex, BigInteger sum, int remainCount)
 {
  if (sum.compareTo(powerOf10[length]) >= 0)
  {
   return;
  }

  if (remainCount == 0)
  {
   // 沒數(shù)可選時
   if (sum.compareTo(powerOf10[length - 1]) > 0 && check(sum))
   {
   results.add(sum);
   }
   return;
  }

  if (!preCheck(currentIndex, sum, remainCount))
  {
   return;
  }

  if (sum.add(preTable1[currentIndex][remainCount]).compareTo(powerOf10[length - 1]) < 0)// 見結束條件2
  {
   return;
  }

  if (currentIndex == 0)
  {
   // 選到0這個數(shù)時的處理
   selected[0] = remainCount;
   search(-1, sum, 0);
  }
  else
  {
   for (int i = 0; i <= remainCount; i++)
   {
   // 窮舉所選數(shù)可能出現(xiàn)的情況
   selected[currentIndex] = i;
   search(currentIndex - 1, sum.add(preTable1[currentIndex][i]), remainCount - i);
   }
  }
  // 到這里說明所選數(shù)currentIndex的所有情況都遍歷了
  selected[currentIndex] = 0;
 }

 /**
 * @param currentIndex
 *   記錄當前正在選擇的數(shù)字(0~9)
 * @param sum
 *   記錄當前值（如選了3個9、2個8 就是9^N*3+8^N*2）
 * @param remainCount
 *   記錄還可選擇多少數(shù)
 * @return 如果當前值符合條件返回true
 */
 private boolean preCheck(int currentIndex, BigInteger sum, int remainCount)
 {
  if (sum.compareTo(preTable1[currentIndex][remainCount]) < 0)// 判斷當前值是否小于PreTable中對應元素的值
  {
   return true;// 說明還有很多數(shù)沒選
  }
  BigInteger max = sum.add(preTable1[currentIndex][remainCount]);// 當前情況的最大值
  max = max.divide(powerOf10[preTable2[currentIndex][remainCount]]);// 取前面一部分比較
  sum = sum.divide(powerOf10[preTable2[currentIndex][remainCount]]);

  while (!max.equals(sum))
  {
   // 檢驗sum和max首部是否有相同的部分
   max = max.divide(BigInteger.TEN);
   sum = sum.divide(BigInteger.TEN);
  }

  if (max.equals(BigInteger.ZERO))// 無相同部分
  {
   return true;
  }

  int[] counter = getCounter(max);

  for (int i = 9; i > currentIndex; i--)
  {
   if (counter[i] > selected[i])// 見結束條件3
   {
   return false;
   }
  }
  for (int i = 0; i <= currentIndex; i++)
  {
   remainCount -= counter[i];
  }
  return remainCount >= 0;// 見結束條件4
 }

 /**
 * 檢查sum是否是花朵數(shù)
 *
 * @param sum
 *   記錄當前值（如選了3個9、2個8 就是9^N*3+8^N*2）
 * @return 如果sum存在于所選集合中返回true
 */
 private boolean check(BigInteger sum)
 {
  int[] counter = getCounter(sum);
  for (int i = 0; i < numberSystem; i++)
  {
   if (selected[i] != counter[i])
   {
   return false;
   }
  }
  return true;
 }

 /**
 * @param value
 *   需要檢驗的數(shù)
 * @return 返回value中0到9出現(xiàn)的次數(shù)的集合
 */
 private int[] getCounter(BigInteger value)
 {
  int[] counter = new int[numberSystem];
  char[] sumChar = value.toString().toCharArray();

  for (int i = 0; i < sumChar.length; i++)
  {
   counter[sumChar[i] - '0']++;
  }

  return counter;
 }

 /**
 * 獲得結果
 * 
 * @return
 */
 public List<BigInteger> getResults()
 {
  return results;
 }

 public static void main(String[] args)
 {
  int num = 21;
  System.err.println("正在求解" + num + "位花朵數(shù)");
  long time = System.nanoTime();
  List<BigInteger> results = NarcissusNumber.search(num);
  time = System.nanoTime() - time;
  System.err.println("求解時間:\t" + time / 1000000000.0 + "s");
  System.err.println("求解結果:\t" + results);
 }
}