一著名軟體公司的java筆試算法題的答案

原題如下：用1、2、2、3、4、5這六個數字，用java寫一個程式，列印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"與"5"不能相連。

 解題思路：

    很明顯，這是一個遞歸算法。我們可以排列将這6個數按從小到大的順序排一下，如果是1,2,3,4,5,6，那麼會有1*2*3*4*5*6= 6!=720個遞增的數。但如果是1,2,2,3,4,5，那麼在這720個數中一定會有相同的數對出現（由于在這6個數中隻有兩個數兩同，也就是說，如果有重複的數，那麼一定是一對數，如122345會出現兩次）。

    排列的基本規則是分步進行。也就是說，要排列上面6個數，首先應該選擇第一個數，這第一個數可以選擇這6個數中的任意一個，如選擇1.第二步是選擇第二個數，這第二個數不能再選擇已經選過的數，如1.是以，它隻能從後面5個數中選擇。如選擇2。以此類推。

    我們也可以在程式中模拟這一過程。源程式如下：

public class test1

{

    private int[] numbers = new int[]

    { 1, 2, 3, 3, 4, 5 };

    public int n;

    private String lastResult = "";

    private boolean validate(String s)

    {

        if (s.compareTo(lastResult) <= 0)

            return false;

        if (s.charAt(2) == '4')

        if (s.indexOf("35") >= 0 || s.indexOf("53") >= 0)

        return true;

    }

    public void list(String index, String result)

        for (int i = 0; i < numbers.length; i++)

        {

            if (index.indexOf(i + 48) < 0)

            {

                String s = result + String.valueOf(numbers[i]);

                if (s.length() == numbers.length)

                {

                    if (validate(s))

                    {

                        System.out.println(s);

                        lastResult = s;

                        n++;

                    }

                    break;

                }

                list(index + String.valueOf(i), s);

            }

        }

    public static void main(String[] args)

        test1 t = new test1();

        t.list("", "");

        System.out.println("總數：" + t.n);

}

    其中list函數是這個算法的核心函數。index參數表示已經選擇過的數，用numbers數組的索引表示。如index="012"，表示numbers的前三個數已經被選擇，也表示應該選擇第四個數了，而這第四個數應該從後三個數中選擇。result參數表示臨時的數字組合（這個數字組合最多是5個數字，因為，如果到了6個數字，就表示已經有一個結果産生了）。在預設情況下index和result的值都是""。

    在validate中使用了  if (s.compareTo(lastResult) <= 0)進行判斷，由于按這種方法進行排列，如果這6個數是遞增給出的，那麼排列的結果一定是遞增的，但上述的6個數其中第2和第3個位置上都是2,是以，如果出現了上一個結果不小于目前結果的情況，一定是有重複了，是以，要将這部分數過濾出去。

使用1, 2, 2, 3, 4, 5的測試結果

122345

122543

123245

123254

123425

123452

125234

125243

125423

125432

132245

132254

132425

132452

132524

132542

142325

142523

143225

143252

145223

145232

152234

152243

152324

152342

152423

152432

212345

212543

213245

213254

213425

213452

215234

215243

215423

215432

221345

221543

223145

223154

223415

223451

225134

225143

225413

225431

231245

231254

231425

231452

231524

231542

232145

232154

232415

232451

232514

232541

241325

241523

242315

242513

243125

243152

243215

243251

245123

245132

245213

245231

251234

251243

251324

251342

251423

251432

252134

252143

252314

252341

252413

252431

312245

312254

312425

312452

312524

312542

315224

315242

315422

321245

321254

321425

321452

321524

321542

322145

322154

322415

322451

322514

322541

325124

325142

325214

325241

325412

325421

341225

341252

341522

342125

342152

342215

342251

342512

342521

345122

345212

345221

412325

412523

413225

413252

415223

415232

421325

421523

422315

422513

423125

423152

423215

423251

425123

425132

425213

425231

431225

431252

431522

432125

432152

432215

432251

432512

432521

451223

451232

451322

452123

452132

452213

452231

452312

452321

512234

512243

512324

512342

512423

512432

513224

513242

513422

521234

521243

521324

521342

521423

521432

522134

522143

522314

522341

522413

522431

523124

523142

523214

523241

523412

523421

541223

541232

541322

542123

542132

542213

542231

542312

542321

543122

543212

543221

總數：198

使用1,2, 3, 3, 4, 5的測試結果

123345

125433

132345

132543

133245

133254

133425

133452

143325

145233

152334

152343

152433

213345

215433

231345

231543

233145

233154

233415

233451

243315

245133

251334

251343

251433

312345

312543

313245

313254

313425

313452

315234

315243

315423

315432

321345

321543

323145

323154

323415

323451

325134

325143

325413

325431

331245

331254

331425

331452

331524

331542

332145

332154

332415

332451

332514

332541

341325

341523

342315

342513

343125

343152

343215

343251

345123

345132

345213

345231

413325

415233

423315

425133

431325

431523

432315

432513

433125

433152

433215

433251

451233

451323

451332

452133

452313

452331

512334

512343

512433

513234

513243

513324

513342

513423

513432

521334

521343

521433

523134

523143

523314

523341

523413

523431

541233

541323

541332

542133

542313

542331

543123

543132

543213

543231

543312

543321

總數：118

使用1, 3, 3, 3, 4, 5的測試結果

133345

313345

315433

331345

331543

333145

333154

333415

333451

343315

345133

433315

451333

513334

513343

513433

541333

543133

543313

543331

總數：20

 本文轉自 androidguy 51CTO部落格，原文連結：http://blog.51cto.com/androidguy/216449，如需轉載請自行聯系原作者